[bzoj4161]Shlw loves matrix I

时间：2022-03-23 18:16:14
来自FallDream的博客，未经允许，请勿转载，谢谢。
给定数列 {hn}前k项，其后每一项满足
hn = a1*h(n-1) + a2*h(n-2) + ... + ak*h(n-k)
其中 a1,a2...ak 为给定数列。请计算 h(n)，并将结果对 1000000007 取模输出。
n<=10^9,k<=2000
 
很裸的特征多项式优化矩阵乘法，打个模版。
#include<iostream>

#include<cstdio>

#define mod 1000000007

#define MN 2000

using namespace std;

int X,F;char ch;

inline int read()

{

    X =  , F =  , ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') F = ;  ch = getchar();}

    while(ch >= '' && ch <= ''){X = X *  + ch - '';ch = getchar();}

    return F?-X:X;

}

int n,k,ans=;

int h[MN+],a[MN*+],b[MN*+],c[MN*+],t[MN*+];

void mul(int*A,int*B)

{

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

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

            c[i+j-]=(c[i+j-]+1LL*A[i]*B[j])%mod;

    for(int i=k<<;i>k;c[i--]=)

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

            c[i-j]=(c[i-j]+1LL*c[i]*t[j])%mod;

    for(int i=k;i;i--) A[i]=c[i],c[i]=;

}

int main()

{

    n=read();k=read();a[]=b[]=;

    for(int i=;i<=k;i++)(t[i]=read())<?t[i]+=mod:;

    for(int i=;i<=k;i++)(h[i]=read())<?h[i]+=mod:;

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

    for(int i=n;i;i>>=,mul(a,a))

        if(i&)mul(b,a);

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

    printf("%d\n",ans);

    return ;

}

相关文章