12042 - Colorful Eggs

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

12042 - Colorful Eggs

Post by Repon kumar Roy » 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;
}

Post Reply

Return to “Volume 120 (12000-12099)”