神秘莫测的bug,一个是不知道怎么Wa的一个是不知道怎么A的。。。。。
喜欢重写代码也是有原因的嘛。
矩阵快速幂。比赛的时候想过,但是没有往矩阵方面想,现在觉得矩阵好神奇。有公式的计算,若是计算次数大,都应想到建立矩阵加速计算。
可以建立矩阵
10 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 0 |
0 | 0 | 0 | 0 | 1 |
然后右乘矩阵(列向量)(233,46,17,23,3)这样,随后一个3 是用来构成2333的。
#include <stdio.h> #include <string.h> #define ll __int64 #define maxn 20 struct node { ll mat[maxn][maxn]; }; int n,m; ll mod; struct node mul(node a,node b) { int i,j,k; node c; for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) c.mat[i][j]=0; for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) for(k=0;k<=n+1;k++) if(a.mat[i][k]&&b.mat[k][j]) c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]%mod)%mod; return c; }; struct node solve(node a) { int i,j,k; node res; for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) if(i==j)res.mat[i][j]=1; else res.mat[i][j]=0; while(m) { if(m&1) res=mul(res,a); m>>=1; a=mul(a,a); } return res; } int main() { mod=10000007; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); while(scanf("%d%d",&n,&m)!=EOF) { int i,j,k; ll a[maxn]; node b,c; for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) b.mat[i][j]=0; ll sum=0; a[0]=233;a[n+1]=3; for(i=1;i<=n;i++) scanf("%I64d",&a[i]); b.mat[0][0]=10;b.mat[0][n+1]=1; for(i=1;i<=n;i++) for(j=0;j<=i;j++) b.mat[i][j]=1; b.mat[n+1][n+1]=1; c=solve(b); for(j=0;j<=n+1;j++) sum+=c.mat[n][j]*a[j]%mod; printf("%I64d\n",sum%mod); } return 0; }