Page 1 of 1

### 12042 - Colorful Eggs

Posted: Tue Feb 25, 2014 8:49 pm
GIve me some Critical Input

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 1000000007

struct matrix {
ll value[65][65];
ll row,col;
};

matrix multiply(matrix a, matrix b)
{
matrix ret;
ret.row=a.row;
ret.col=b.col;
ll sum;
for (int i=0; i<ret.row; i++) {
for (int j=0; j<ret.col; j++) {
sum=0;
for (int k=0; k<a.col; k++) {
sum+= a.value[i][k]* b.value[k][j];
sum %=mod;
}
ret.value[i][j]=sum;
}

}
return ret;
}
matrix matrixExpo(matrix a, long long p)
{
matrix result;
result.row=a.row;
result.col=a.col;
for (int i=0; i<result.row; i++) {
for(int j=0;j<result.col;j++){
if(i==j)result.value[i][i]=1;
else result.value[i][j]=0;
}
}
while (p) {
if(p&1){
result=multiply(result, a);
p--;
}
a=multiply(a, a);
p/=2;
}
return result;
}

ll ara[65],ans[65];
int main()
{
ll m,n,d,sum;
matrix a;
cin>>m;
while (m--) {
scanf("%lld %lld",&n,&d);
for (ll i=n-1; i>-1; i--) {
scanf("%lld",&ara[i]);
}
a.row=n;
a.col=n;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if(i==0){
a.value[i][j]=1;
}
else if(j==0) a.value[i][j]=1;
else if (j<=i) a.value[i][j]=0;
else a.value[i][j]=1;
}
}
if(d>1){
a=matrixExpo(a,d-1);
for (int i=0; i<n; i++) {
sum=0;
for (int j=0; j<n; j++) {
sum+= (a.value[i][j]*ara[j])%mod;
}
ans[i]=sum;
}
}
else {
for (int i=0; i<n; i++) {
ans[i]=ara[i];
}
}

printf("%lld",ans[n-1]);
for (ll i=n-2; i>-1; i--) {
printf(" %lld",ans[i]);
}
printf("\n");

}

return 0;
}
``````