这个东西一开始没咋看懂记录一下。。。

比如一个式子
可以用分治的方法解决:








同样,类比的,矩阵的等比数列也可以用分治法求解:

类比一下是一样的:

#include<bits/stdc++.h>

using namespace std; 
const int N = 35; 

struct Matrix 
{ 
    int m[N][N]; 
}; 

Matrix I; 
int n,k,M; 

Matrix add(Matrix a,Matrix b) 
{ 
    Matrix c; 
    for(int i=0; i<n; i++) 
    { 
        for(int j=0; j<n; j++) 
        { 
            c.m[i][j] = a.m[i][j] + b.m[i][j]; 
            c.m[i][j] %= M; 
        } 
    } 
    return c; 
} 

Matrix multi(Matrix a,Matrix b) 
{ 
    Matrix c; 
    for(int i=0; i<n; i++) 
    { 
        for(int j=0; j<n; j++) 
        { 
            c.m[i][j] = 0; 
            for(int k=0; k<n; k++) 
                c.m[i][j] += a.m[i][k] * b.m[k][j]; 
            c.m[i][j] %= M; 
        } 
    } 
    return c; 
} 

Matrix power(Matrix A,int n) 
{ 
    Matrix ans = I,p = A; 
    while(n) 
    { 
        if(n & 1) 
        { 
            ans = multi(ans,p); 
            n--; 
        } 
        n >>= 1; 
        p = multi(p,p); 
    } 
    return ans; 
} 

Matrix sum(Matrix A,int k) 
{ 
    if(k == 1) return A; 
    Matrix t = sum(A,k/2); 
    if(k & 1) 
    { 
        Matrix cur = power(A,k/2+1); 
        t = add(t,multi(t,cur)); 
        t = add(t,cur); 
    } 
    else 
    { 
        Matrix cur = power(A,k/2); 
        t = add(t,multi(t,cur)); 
    } 
    return t; 
} 

int main() 
{ 
    while(scanf("%d%d%d",&n,&k,&M)!=EOF) 
    { 
        Matrix A; 
        for(int i=0; i<n; i++) 
        { 
            for(int j=0; j<n; j++) 
            { 
                scanf("%d",&A.m[i][j]); 
                A.m[i][j] %= M; 
                I.m[i][j] = (i==j); 
            } 
        } 
        Matrix ans = sum(A,k); 
        for(int i=0; i<n; i++) 
        { 
            for(int j=0; j<n; j++) 
                printf("%d ",ans.m[i][j]); 
            puts(""); 
        } 
    } 
    return 0; 
}

3 对 “等比数列二分求和”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注