k阶线性递推-特征多项式

BZOJ4161

http://www.lydsy.com/JudgeOnline/problem.php?id=4161

#include<cstdio>
typedef long long ll;
const int mod=1e9+7;
const ll up=(1ll<<31);
int n,k,ans,x;
int u[4010];
struct poly{
	ll a[4010];
	poly(){
		for(register int i=0;i<k+k-1;++i)
			a[i]=0;
	}
	inline ll &operator[](int x){
		return a[x];
	}
	friend inline poly operator*(poly A,poly B){
		register poly ret;
		for(register int i=0;i<k;++i)
			for(register int j=0;j<k;++j){
				ret[i+j]+=1ll*A[i]*B[j];
				if(ret[i+j]>=up)
					ret[i+j]%=mod;
			}
		for(register int i=0;i<k+k-1;++i)
			ret[i]%=mod;
		for(register int i=k+k-2;i>=k;--i){
			for(register int j=0;j<k;++j){
				ret[i-j-1]+=1ll*ret[i]*u[j];
				if(ret[i-j-1]>=up)
					ret[i-j-1]%=mod;
			}
			ret[i]=0;
		}
		for(register int i=0;i<k;++i)
			ret[i]%=mod;
		return ret;
	}
}f,s;
int main(){
	scanf("%d%d",&n,&k);
	for(register int i=0;i<k;++i)
		scanf("%d",u+i),u[i]=(u[i]%mod+mod)%mod;
	for(f[1]=s[0]=1;n;n>>=1,f=f*f)if(n&1)s=s*f;
	for(register int i=0;i<k;++i)s[i]%=mod;
	for(register int i=0;i<k;++i)scanf("%d",&x),ans=((ans+1ll*x*s[i]%mod)%mod+mod)%mod;
	printf("%d
",ans);
	return 0;
}