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 = 233,a = 2333,a = 23333...) Besides, in 233 matrix, we got a = a +a ( i,j ≠ 0). Now you have known a ,a ,...,a , could you tell me a 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 ). The second line contains n integers, a ,a ,...,a (0 ≤ a < 2 ).OutputFor each case, output a mod 10000007.Sample Input
1 1
1
2 2
0 0
3 7
23 47 16
Sample Output
234
2799
72937 题意：
a[i][j]=a[i-1][j]+a[i][j-1];
a[0][1]=233,a[0][2]=2333,a[0][3]=23333,......
a[1][0]到a[n][0]由输入给出，求a[n][m];
思路：
本来打算直接用a[i][j]=a[i-1][j]+a[i][j-1]作为公式进行推导，发现并不可行。
实际上是直接对每一列进行操作。
写完这题，大概矩阵快速幂才是真的入门。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int maxm = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); ll num[]; struct Matrix{
ll mp[][];
};
Matrix mul(Matrix a,Matrix b,int n){
Matrix ans;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
ans.mp[i][j]=;
for(int k=;k<=n;k++){
ans.mp[i][j]+=a.mp[i][k]*b.mp[k][j];
}
ans.mp[i][j]%=mod;
}
}
return ans;
} Matrix q_pow(Matrix a,int b,int n){
Matrix ans;
memset(ans.mp,,sizeof(ans.mp));
for(int i=;i<=n;i++){
ans.mp[i][i]=;
}
while (b){
if(b&){
ans=mul(ans,a,n);
}
b>>=;
a=mul(a,a,n);
}
return ans;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++){
scanf("%lld",&num[i]);
}
Matrix exa;
memset(exa.mp,,sizeof(exa.mp));
int t=;
exa.mp[n+][n+]=;
for(int i=;i<=n+;i++){
exa.mp[i][]=;exa.mp[i][n+]=;
for(int j=;j<=t;j++){
exa.mp[i][j+]=;
}
t++;
}
exa=q_pow(exa,m,n+);
ll ans=;
num[]=;num[n+]=;
for(int i=;i<=n+;i++){
ans+=exa.mp[n+][i]*num[i-];
ans%=mod;
}
printf("%lld\n",ans); } return ;
}