bzoj4161 (k^2logn求线性递推式)

分析：

　　我们可以写把转移矩阵A写出来，然后求一下它的特征多项式，经过手动计算应该是这样的p(x)=$x^k-\sum\limits_{i=1}^ka_i*x^{k-i}$

　　根据Cayley-Hamilton定理可得，p(A)=0

　　他表示$A^n = f(A) * p(A) + g(A)$

　　第一项的值是0，所以即$A^n=g(A)$，其中f(A) g(A)都是关于A的多项式，f(A)是多项式除法的商，g(A)是余数

　　我们考虑$x^n$这个多项式，我们去求出它对于$p(A)$的余数多项式$g(A)$，那么$A^n$就等价于了$g(A)$，注意到新的多项式次数就很低了，不超过k-1

　　我们要求的是$A^nH=\sum\limits_{i=0}^{k-1}c_i*A^i*H$的第一个元素，注意到$A^i*H$相当于把H又递推了i次

　　所以结果等价于$A^nH=\sum\limits_{i=0}^{k-1}c_i*A^i*H$

　　时间复杂度$O(k^2 log n)$，但常数很大

　　中间的多项式取模和递推可以用FFT来优化，但常数更巨大

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=,mod=;

 int a[maxn+],p[maxn+],ans[maxn+],num[maxn+];

 int h[maxn+],tmp[maxn+];

 int n,k;

 void mul(int *a,int *b,int *ans)

 {

     for(int i=;i<=*k;++i) tmp[i]=;

     for(int i=;i<k;++i)

         for(int j=;j<k;++j)

             tmp[i+j]=(tmp[i+j]+1LL*a[i]*b[j])%mod;

     for(int i=*k-;i>=k;--i)

     {

         for(int j=k-;j>=;--j)

             tmp[i-k+j]=(tmp[i-k+j]-1LL*tmp[i]*p[j])%mod,tmp[i-k+j]=(tmp[i-k+j]+mod)%mod;

         tmp[i]=;

     }

     for(int i=;i<k;++i) ans[i]=tmp[i];

 }

 int main()

 {

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

     for(int i=;i<=k;++i) scanf("%d",&a[i]);

     for(int i=;i<k;++i) scanf("%d",&h[i]);

     p[k]=;

     for(int i=;i<=k;++i) p[k-i]=mod-a[i];

     for(int i=k;i<*k;++i)

         for(int j=;j<=k;++j)

         {

             h[i]=h[i]+1LL*h[i-j]*a[j]%mod;

             h[i]%=mod;

         }

     if(n<*k) return *printf("%d\n",h[n]);

     int b=n-k+;

     num[]=,ans[]=;

     while(b)

     {

         if(b&) mul(ans,num,ans);

         mul(num,num,num);

         b>>=;

     }

     long long res=;

     for(int i=;i<k;++i) res=(res+1LL*ans[i]*h[i+k-])%mod;

     printf("%lld\n",(res+mod)%mod);

     return ;

 }