Description
给定数列 {hn}前k项，其后每一项满足
hn = a1h(n-1) + a2h(n-2) + ... + ak*h(n-k)
其中 a1,a2...ak 为给定数列。请计算 h(n)，并将结果对 1000000007 取模输出。
Solution
常系数线性齐次递推
首先 \(A\) 的特征多项式是 \(x^k-\sum_{i=1}^{k}a_i*x^{k-i}\)
根据Cayley-Hamilton定理可以得到 \(f(A)=0\)
\(A^n=A^n\mod f(A)\)
以上并不知道怎么得来的....QwQ
于是我们可以快速幂求出 \(x^1,x^2.....x^n\) 的系数 \(c_i\),然后代入 \(A\)
最后答案就是 \(A^n*h_k=\sum_{i=0}^{k-1}c_i*A^i*h_k=\sum_{i=0}^{k-1}c_i*h_{i+k}\)
关于多项式取模法则:
如:\(5x^5+3x^4+x^3+x^2+6x+1 \mod (x^3+x^2+x+1)\)
我们先把 \((x^3+x^2+x+1)\) 乘以 \(x^2\),把被除的多项式中的 \(5x^5\) 消掉(做减法)
然后以此把次高位消掉,直到消到 \(x^3\) 为止,此题中可以 \(O(k^2)\) 暴力多项式取模
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=4010,mod=1e9+7;
int n,k,a[N],h[N],mo[N],ans[N],b[N],t[N];
inline void mul(int *a,int *b,int *c){
for(int i=2*k-2;i>=0;i--)t[i]=0;
for(int i=0;i<k;i++)
if(a[i])
for(int j=0;j<k;j++)
t[i+j]=(t[i+j]+1ll*a[i]*b[j])%mod;
for(int i=2*k-2;i>=k;i--)//多项式取模,依次消掉最高位
if(t[i])
for(int j=k-1;j>=0;j--)
t[i-k+j]=(t[i-k+j]-1ll*mo[j]*t[i]+mod)%mod;
for(int i=0;i<k;i++)c[i]=t[i];
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=k;i++)gi(a[i]),mo[k-i]=mod-a[i];
for(int i=1;i<=k;i++)gi(h[i]);
mo[k]=1;b[1]=1;ans[0]=1;
for(n-=k-1;n;n>>=1){
if(n&1)mul(ans,b,ans);
mul(b,b,b);
}
for(int i=k+1;i<=2*k-1;i++)
for(int j=1;j<=k;j++)h[i]=(h[i]+1ll*h[i-j]*a[j])%mod;
int ret=0;
for(int i=0;i<k;i++)ret=(ret+1ll*h[i+k]*ans[i])%mod;
if(ret<0)ret+=mod;
cout<<ret<<endl;
return 0;
}