hdu5015构造转移矩阵

时间：2024-08-29 14:33:32
/*

构造转移矩阵：

先推公式：

    首先是第0行：A[0][j+1]=A[0][j]*10+3

    1-n行： A[i][j+1]=A[i][j]+A[i-1][j+1]=...

                    =A[i][j]+A[i-1][j]+...+A[1][j]+A[0][j+1]

    所以第j+1行状态可以由第j行通过乘上一个转移矩阵得到

那么就是转移矩阵的构造

设F[j]为第j列，F[j+1]为第j+1列,B为转移矩阵

    有 F[j+1]=B*F[j]

    按照递推性质

1  0  0  0  0  ...  0   3           3

1  10 0  0  0  ...  0   A[0][j]     A[0][j+1]

1  10 1  0  0  ...  0 * A[1][j]  =  A[1][j+1]

1  10 1  1  0  ...  0   A[2][j]       .

1  10 1  1  1  ...  0   A[3][j]       .

1  10 1  1  1  ...  1   A[n][j]     A[n][j+1]

规定初始数组F[0]=[3,233,a1,a2...an]

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 10000007

ll F[],a[];

ll n,m;

struct Mat{

    ll m[][];

    Mat(){memset(m,,sizeof m);}

};

void mul1(Mat A,ll F[]){

    ll B[]={};

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

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

            B[i]=(B[i]+A.m[i][j]*F[j]%mod)%mod;

    memcpy(F,B,sizeof B);

}

void mul2(Mat & A,Mat B){

    Mat C;

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

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

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

                C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j]%mod)%mod;

    memcpy(A.m,C.m,sizeof C.m);

}

int main(){

    while(cin>>n>>m){

        F[]=,F[]=;

        for(int i=;i<n+;i++)cin>>F[i];

        Mat A,B;

        for(int i=;i<n+;i++)A.m[i][]=;

        for(int i=;i<n+;i++)A.m[i][]=;

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

            for(int i=j;i<n+;i++)

                A.m[i][j]=;

        while(m){

            if(m%)

                mul1(A,F);

            mul2(A,A);

            m>>=;

        }

        cout<<F[n+]<<endl;

    }

}

相关文章