bzoj 4161: Shlw loves matrixI

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;

}