vijosP1067Warcraft III 守望者的烦恼

链接：https://vijos.org/p/1067

【思路】

矩阵乘法。

可以得出递推式：

f[i]=sum{ f[n-1],f[n-2]…f[n-k] }

矩阵乘法加速转移如下：

1、原始矩阵F 1 x k：

| 1,0,0,0,0,…|

2、转移矩阵T k x k：

| 1 , 0, … |

| 1, 1 , … |

| 1, 0, 1,0 |

| 1 0, 0, 1 |

即有如下转移：

vijosP1067Warcraft III 守望者的烦恼-LMLPHP

（上图转移矩阵有错）

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define FOR(a,b,c) for(int a=(b);a<(c);a++)

 using namespace std;

 const int maxn = +;

 const int MOD=;

 struct Matrix{

     int r,c;

     long long N[maxn][maxn];

     void init(int r,int c) {

         this->r=r, this->c=c;

         memset(N,,sizeof(N));

     }

     Matrix operator*(Matrix& B)const{

         Matrix A=*this,C;

         C.init(A.r,B.c);

         for(int i=;i<C.r;i++)

            for(int j=;j<C.c;j++)

               for(int k=;k<A.c;k++)

                  C.N[i][j] = (C.N[i][j]+A.N[i][k]*B.N[k][j])%MOD;

         return C;

     }

     Matrix pow(int p) {

         Matrix tmp=*this;

         Matrix ans;

         ans.init(r,r);

         for(int i=;i<r;i++) ans.N[i][i]=;

         while(p) {

             if(p&) ans=ans*tmp;

             tmp=tmp*tmp;

             p>>=;

         }

         return ans;

     }

 };

 int n,k;

 int main() {

     scanf("%d%d",&k,&n);

     Matrix F,T;

     T.init(k,k);

     FOR(i,,k) T.N[i][]=;

     FOR(i,,k) T.N[i-][i]=;

     T=T.pow(n);

     F.init(,k);

     F.N[][]=;

     F=F*T;

     printf("%d\n",F.N[][]);

     return ;

 }