lightoj1006

CODE

#include <bits/stdc++.h>

using namespace std;

const int mod= 10000007;
class matrix
{
public:
        int r;
        int c;
        vector<vector<long long> >m;
        matrix(int _r, int _c): c(_c), r(_r)
        {
                m.resize(r);
                for(int i=0;i<r;i++)
                        m[i].resize(c);
        }
        matrix operator *(const matrix& ob)
        {
                matrix m(r, ob.c);
                for (int i = 0; i < r; i++)
                        for (int j = 0; j < ob.c; j++)
                        {
                                m.m[i][j] = 0;
                                for (int k = 0; k < c; k++)
                                        m.m[i][j] = (m.m[i][j]+this->m[i][k] * ob.m[k][j])%mod;
                        }
                return m;
        }
        matrix operator +(const matrix& ob)
        {
                matrix m(r, c);
                for (int i = 0; i < r; i++)
                        for (int j = 0; j < c; j++)
                                m.m[i][j]=(this->m[i][j]+ob.m[i][j])%mod;
                return m;
        }
        void unit()
        {
                for (int i = 0; i < r; i++)
                {
                        for(int j=0;j<c;j++)
                                m[i][j]=0;
                        m[i][i] = 1;
                }
                return;
        }
        matrix operator ^(int n)
        {
                matrix ans(r, c);
                matrix m(r,c);
                m = (*this);
                ans.unit();
                while (n)
                {
                        if (n & 1)
                                ans = ans * m;
                        m = m * m;
                        n >>= 1;
                }
                return ans;

        }
        void display()
        {
                for (int i = 0; i < r; i++)
                {
                        for (int j = 0; j < c; j++)
                                printf("%10lld", m[i][j]);
                        cout << endl;
                }
        }
};
int a[7],n;
int main()
{
        int t;
        cin >> t;
        for(int nCase = 1;nCase <=t;nCase++)
        {
                cout << "Case "<<nCase<<": ";
                matrix m(6,6);
                int tp[][6]={1,1,0,0,0,0,
                             1,0,1,0,0,0,
                             1,0,0,1,0,0,
                             1,0,0,0,1,0,
                             1,0,0,0,0,1,
                             1,0,0,0,0,0};
                for(int i=0;i<6;i++)
                        for(int j=0;j<6;j++)
                                m.m[i][j]=tp[i][j];
                //m.display();
                for(int i=0;i<6;i++)
                        cin >> a[i];
                cin >> n;
                if(n<6){ cout <<a[n]%mod<<endl;continue;}
                matrix p(1,6);
                for(int i=0;i<6;i++)
                        p.m[0][5-i]=a[i];
                //p.display();
                m=m^(n-5);
                p=p*m;
                cout << p.m[0][0]%mod<<endl;

        }
}