BZOJ 4161 Shlw loves matrixI ——特征多项式

矩阵乘法递推的新姿势。

叉姐论文里有讲到

利用特征多项式进行递推，然后可以做到k^2logn

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define p 1000000007

ll c[4010];

int n,k,u[2010],ans,x,cnt;

struct  P{int s[2010];}f,t;

void mult(P & a,const P & b)

{

    F(i,0,k+k-2) c[i]=0;

    F(i,0,k-1) F(j,0,k-1)

    {

        c[i+j]+=1LL*a.s[i]*b.s[j];

        if (c[i+j]>=1LL<<62) c[i+j]%=p;

    }

    D(i,k+k-1,0) if (c[i]%=p,i>=k)

    {

        F(j,0,k-1)

        {

            c[i-1-j]+=c[i]*u[j];

            if (c[i-1-j]>=1LL<<62) c[i-1-j]%=p;

        }

        c[i]=0;

    }

    F(i,0,k-1) a.s[i]=c[i];

}

int main()

{

    scanf("%d%d",&n,&k);

    F(i,0,k-1)

    {

        scanf("%d",&u[i]);

        u[i]=(u[i]%p+p)%p;

    }

    for (t.s[1]=f.s[0]=1;n;n>>=1,mult(t,t)) if (n&1) mult(f,t);

    F(i,0,k-1)

    {

        scanf("%d",&x);

        x=(x%p+p)%p;

        ans=(ans+1LL*x*f.s[i])%p;

    }

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

}