前些天做了比赛，学到了矩阵连乘，直到今天才真正弄懂了。 TJU3318  Chinese rings，这就是简单的矩阵连乘的应用。 当然，学习这个首先要知道二分求幂。 我构造的矩阵是这样的，矩阵A: 1  2  1 1  0  0 0  0  1 起始矩阵是，矩阵B: f(2) f(1) 1 目标矩阵是矩阵C: f(n+1) f(n) 1 这样矩阵A*B就可得到矩阵 f(3) f(2) 1 A*（A*B）又可得到 f(4) f(3) 1 . . . . . 我感觉很巧妙，也是今天才刚刚体会的。 这样的话 A*A*A....*A*B就可以得到C，然后就得到我们的答案f(n) 我们可以先把前面n-1个A求出来，这里用到二分求幂的方法。 关于二分求幂，我刚开始也不懂。后来去网上搜了下才知道。 话不多说，上代码。 #include <stdio.h>#include <string.h>#define M 200907 void mulmatrix(__int64 a[][3],__int64 b[][3]){    int i,j,k;    __int64 c[3][3];    memset(c,0,sizeof(c));    for(i = 0;i < 3;i++)        for(j = 0;j < 3;j++)            for(k = 0;k < 3;k++)                c[i][j] = ( c[i][j] + ( ( a[i][k] * b[k][j] ) % M) ) % M;    for(i = 0;i < 3;i++)        for(j = 0;j < 3;j++)            a[i][j] = c[i][j];} void pf(int n,__int64 ans[][3],__int64 a[][3]){    int t;    while(n != 0)    {        t = n % 2;        n /= 2;        if(t != 0)            mulmatrix(ans,a);        mulmatrix(a,a);    }}   int main(){    int n,i,j;    while(scanf("%d",&n) != EOF && n != 0)    {        __int64 a[3][3] = {1,2,1,1,0,0,0,0,1},ans[3][3] = {1,0,0,0,1,0,0,0,1},c[3] = {2,1,1},res;        if(n > 2)        {            pf(n-1,ans,a);            res = 0;            for(i = 0;i < 3;i++)                res = ( res + ( ans[1][i] *  c[i] ) % M ) % M;        }        else            res = n;        printf("%d\n",res);    }    return 0;}

评论