bzoj 4161 Shlw loves matrixI【常系数线性齐次递推】

并不会递推，不过板子挺好背的，只要是类似的递推都能用，但是注意c数组不能使负数

如果除了递推还有常数项的话，就用f[i]-f[i-1]的方式消掉常数项（然后多一个f[i-1]的项）

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

const int N=4005,mod=1000000007;

int n,m,a[N],ans[N],c[N],d[N],f[N],an;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void jia(int &x,int y)

{

    x+=y;

    x>=mod?x-=mod:0;

}

int ksm(int a,int b)

{

    int r=1;

    while(b)

    {

        if(b&1)

            r=1ll*r*a%mod;

        a=1ll*a*a%mod;

        b>>=1;

    }

    return r;

}

void mul(int a[],int b[])

{

    memset(d,0,sizeof(d));

    for(int i=0;i<=m;i++)

        for(int j=0;j<=m;j++)

            jia(d[i+j],1ll*a[i]*b[j]%mod);

    for(int i=2*m;i>=m;i--)

    {

        for(int j=0;j<m;j++)

            jia(d[i-m+j],1ll*d[i]*c[m-j]%mod);

        d[i]=0;

    }

    for(int i=0;i<=2*m;i++)

        a[i]=d[i];

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=m;i++)

		c[i]=(read()+mod)%mod;

	for(int i=0;i<m;i++)

		f[i]=(read()+mod)%mod;

	a[1]=1,ans[0]=1;

	while(n)

	{

		if(n&1)

			mul(ans,a);

		mul(a,a);

		n>>=1;

	}

	for(int i=0;i<m;i++)

		jia(an,1ll*f[i]*ans[i]%mod);

	printf("%lld\n",an);

    return 0;

}