UVA : 11486 - Finding Paths in Grid (Matrix expo, math)

UVA : 11486 - Finding Paths in Grid (Matrix expo, math)

///==================================================///
///               !! HELLO WORLD !!                  ///
///           IT'S ME - BISHAL GAUTAM                ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb(x) push_back(x)
#define nl printf("\n")
#define Max(a,b) ((a>b)?a:b)
#define Min(a,b) ((a<b)?a:b)
#define SZ(x) (int)(x.size())
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     38
#define inf    2000000010
#define eps    1e-9
#define MD     1000000007
///===============================///

#define N 37
int ms;///Matrix Size GLOBAL: N
struct mat {
    ll m[N][N];
    mat() {};
    void Nullify( ) {
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                m[i][j]=0;
            }
        }
    }
    void Unify( ) {
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                m[i][j]=(i==j);
            }
        }
    }
    mat operator *(const mat &b )const {
        mat c;
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                c.m[i][j]=0;
                for(int k=0; k<ms; k++) {
                    c.m[i][j]=( c.m[i][j]+ (m[i][k]*b.m[k][j])%MD )%MD;
                }
            }
        }
        return c;
    }
    mat Pow(int p) {
        mat ret;
        ret.Unify();
        mat B=(*this);
        for(; p; p>>=1) {
            if(p & 1)ret = (ret * B);
            B = (B * B);
        }
        return ret;
    }
    void Print( ) {
        cout<<endl;
        cout<< "Matix is:\n";
        cout<< "****************************\n";
        for(int i=0; i<ms; i++) {
            for(int j=0; j<ms; j++) {
                cout<<m[i][j]<< "  ";
            }
            cout<<endl;
        }
        cout<< "****************************\n";
        cout<<endl;
    }
} b;

int MP[7][7][7][7];
vector< vector<int> >v;
void Precal( ) {
    for(int a=0; a<7; a++) {
        for(int b=a+1; b<7; b++) {
            for(int c=b+1; c<7; c++) {
                for(int d=c+1; d<7; d++) {
                    vector<int>tp;
                    tp.pb(a);
                    tp.pb(b);
                    tp.pb(c);
                    tp.pb(d);
                    v.pb( tp );
                }
            }
        }
    }
    ms=SZ(v);
    for(int i=0; i<ms; i++) {
        MP[ v[i][0] ][ v[i][1] ][ v[i][2] ][ v[i][3] ]=i;
        for(int j=0; j<ms; j++) {
            vector<int>tmp=v[j];
            int tot=0;
            do {
                int cnt=0;
                for(int k=0; k<4; k++) {
                    if( abs( v[i][k]-tmp[k] ) ==1 )cnt++;
                }
                if(cnt==4) tot++;

            } while( next_permutation(all(tmp)) );

            b.m[ i ][ j ]=tot;
        }
    }
}


int a[10];
int main() {
    int tc,cs=1,i,j,k,n,r,x;
    b.Nullify();
    Precal( );
    S(tc);
    while(tc--) {
        S(n);
        CLR(a);
        k=0;
        for(i=0;i<7;i++){
            S(x);
            if(x)a[k++]=i;
        }
        int id=MP[ a[0] ][ a[1] ][ a[2] ][ a[3] ];
        n--;
        mat ret=b.Pow( n );
        ll ans=0;
        for(i=0;i<ms;i++){
            ans=(ans+ret.m[ id ][ i ])%MD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}