In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,m in the 233 matrix?
InputThere are multiple test cases. Please process till EOF. For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).OutputFor each case, output a n,m mod 10000007.Sample Input
1 1 1 2 2 0 0 3 7 23 47 16Sample Output
234 2799 72937Hint
#include<bits/stdc++.h> #define MAX 15 #define MOD 10000007 using namespace std; typedef long long ll; ll n,m; struct mat{ ll a[MAX][MAX]; }; mat operator *(mat x,mat y) { mat ans; memset(ans.a,0,sizeof(ans.a)); for(int i=1;i<=n+2;i++){ for(int j=1;j<=n+2;j++){ for(int k=1;k<=n+2;k++){ ans.a[i][j]+=x.a[i][k]*y.a[k][j]%MOD; ans.a[i][j]%=MOD; } } } return ans; } mat qMod(mat a,ll nn) { mat t; memset(t.a,0,sizeof(t.a)); for(int i=1;i<=n+1;i++){ t.a[i][1]=10; for(int j=2;j<=i;j++){ t.a[i][j]=1; } t.a[i][n+2]=1; } t.a[n+2][n+2]=1; while(nn){ if(nn&1) a=t*a; nn>>=1; t=t*t; } return a; } int main() { int t,i,j; while(~scanf("%I64d%I64d",&n,&m)){ mat a; memset(a.a,0,sizeof(a.a)); a.a[1][1]=23; for(i=2;i<=n+1;i++){ scanf("%I64d",&a.a[i][1]); } a.a[n+2][1]=3; a=qMod(a,m); printf("%I64d\n",a.a[n+1][1]); } return 0; }
转载于:https://www.cnblogs.com/yzm10/p/9601323.html
相关资源：数据结构—成绩单生成器