矩阵十大经典标题之七- Warcraft-III-守望者的烦恼

矩阵十大经典题目之七- Warcraft--III--守望者的烦恼

原文：

我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
     
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

根据原文得出的一个矩阵，然后算矩阵的高次幂。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define Nnum 31
#define Mnum 31
#define LL __int64
#define MOD 7777777
using namespace std;
struct matrix
{
    LL mat[11][11];
    matrix(){
        memset(mat,0,sizeof(mat));
    }
};
int nn;
matrix mul(matrix A,matrix B)
{
    int i,j,k;
    matrix C;
    for(i=1;i<=nn;i++)
    {
        for(j=1;j<=nn;j++)
        {
            C.mat[i][j]=0;
            for(k=1;k<=nn;k++)
            {
                C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%MOD;
            }
        }
    }
    return C;
}
matrix powmul(matrix A,int k)
{
    matrix B;
    for(int i=1;i<=nn;i++)B.mat[i][i]=1;
    while(k)
    {
        if(k&1)B=mul(B,A);
        A=mul(A,A);
        k=k/2;
    }
    return B;
}
int main()
{
    int n,k,i,j;
    matrix A;
    matrix B;
    while(~scanf("%d%d",&k,&n))
    {
        nn=k;
        for(i=1;i<=k-1;i++)A.mat[i][i+1]=1;
        for(i=1;i<=k;i++)A.mat[k][i]=1;
        B.mat[0][1]=1;
        for(i=1;i<=k;i++)
            for(j=0;j<i;j++)
                B.mat[i][1]+=B.mat[j][1];
        A=powmul(A,n-1);
        B=mul(A,B);
        cout<<B.mat[1][1]<<endl;
    }
    return 0;
}