题目大意：第一年要交a0克黄金，接下来f1年每年交比前一年多一克的黄金，再接下来f2年每年交前一年两倍的黄金，之后每年都交最近K年交的黄金乘积数量的黄金，问第n年要交多少黄金，答案对1e8+7取模，多组数据。（1<=a0,f1,f2<=50，1<=K<=f1+f2+1，1<=N<=10^9，数据组数<=10）
思路：前f1+f2+1年暴力计算，剩下的每一年交的黄金都可以表示为第f1+f2+2-K到f1+f2+1年各年交的黄金的次幂的乘积，我们用矩阵记录下每一年交的黄金分解这K年的乘积后每一年的次数，数字相乘即为矩阵相加，即可用线性递推关系来表示，可以用矩阵快速幂在O(K^3logN)时间内完成计算，由于多组数据这个复杂度并不能通过，可以使用矩阵特征多项式优化到O(K^2logN)。矩阵特征多项式优化简单来说主要是这样的：例如有数列满足fn=fn-1+fn-2+…+fn-k，那么它的递推矩阵根据相关定理也满足A^n=A^(n-1)+A^(n-2)+…+A^(n-k)，这样A的次幂都可以用A^1、A^2…A^k的线性组合来表示，我们就可以用关于A的k次多项式表示一个矩阵，矩阵相乘相当于这个多项式相乘，得到的A^(k+1)到A^2k项再重新表示为A^1、A^2…A^k，我们就能O(K^2)完成这个矩阵的乘法运算，再用快速幂就能把总时间优化到O(K^2logN)。
#include<cstdio> #include<cstring> #define MN 100 #define MOD 100000007 int a[MN+5],k,t[MN*2+5]; struct pol { int z[MN+5]; pol(){memset(z,0,sizeof(z));} pol operator*(pol b) { int i,j;pol c; memset(t,0,sizeof(t)); for(i=1;i<=k;++i)for(j=1;j<=k;++j) t[i+j]=(t[i+j]+1LL*z[i]*b.z[j])%(MOD-1); for(i=k<<1;i>k;--i)for(j=1;j<=k;++j) t[i-j]=(t[i-j]+t[i])%(MOD-1); for(i=1;i<=k;++i)c.z[i]=t[i]; return c; } }; int pw(int x,int y) { int r=1; for(;y;y>>=1,x=1LL*x*x%MOD)if(y&1)r=1LL*r*x%MOD; return r; } int main() { int T,n,f1,f2,i,x; for(scanf("%d",&T);T--;) { scanf("%d%d%d%d%d",&a[0],&f1,&f2,&k,&n); for(i=1;i<=f1;++i)a[i]=a[i-1]+1; for(i=1;i<=f2;++i)a[f1+i]=(a[f1+i-1]<<1)%MOD; if(--n<=f1+f2){printf("%d ",a[n]);continue;} pol p,t;p.z[1]=t.z[1]=1; for(n-=f1+f2-k+1;n;n>>=1,t=t*t)if(n&1)p=p*t; for(i=x=1;i<=k;++i)x=1LL*x*pw(a[f1+f2-k+i],p.z[i])%MOD; printf("%d ",x); } }