matrix2, C++ (gcc)

matrix2

//AUTHOR : TIRTH JARSANIA
//COLLEGE : DAIICT

#pragma optimize("", off)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:36777216")
#include<bits/stdc++.h>
using namespace std;

#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define pi acos(-1)
#define bp __builtin_popcount
#define ll long long int
#define ld long double
#define pii pair<ll , ll>
#define For(i,a,b) for(ll i=a;i<b;i++)
#define Fori(i,a,b,p) for(ll i=a;i<b;i+=p)
#define Ror(i,a,b) for(ll i=a;i>b;i--)
#define Rori(i,a,b,p) for(ll i=a;i>b;i-=p)

#define precision(x,d) cout<<fixed<<setprecision(d)<<x
#define minQueue priority_queue<pii,vector<pii>,greater<pii> > 
#define maxQueue priority_queue<pii>

#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define FILL(a,b) memset((a),(b),sizeof((a)))
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL))

const ll LN = 24;
const ll M = 1e9;
vector<ll> t1(LN,0) , t2(LN,0);

ll add(ll a,ll b)
{
    ll x = a + b;
    if(x >= M)
        x -= M;
    return x;
}

ll mult(ll a,ll b)
{
    return (a % M * b %M)%M;
}
struct matrix
{
    ll jt[LN][LN];
    
    void reset()
    {
        FILL(jt,0);
    }
    void makeiden()
    {
        reset();
        For(i,0,LN)
            jt[i][i] = 1;
    }
    matrix operator +(matrix &a)
    {
        matrix copy;
        For(i,0,LN)
            For(j,0,LN)
                copy.jt[i][j] = add(jt[i][j],a.jt[i][j]);
        return copy;
    }
    matrix operator *(matrix &a)
    {
        matrix copy;
        copy.reset();
        For(i,0,LN)
            For(j,0,LN)
                For(k,0,LN)
                copy.jt[i][j] = add(copy.jt[i][j],mult(jt[i][k] , a.jt[k][j]));
        return copy;
    }
};

matrix bin_pow(matrix a, ll b)
{
	matrix res;
	res.makeiden();
	while(b > 0)
	{
		if(b & 1)
		{
			res = res * a;
		}
		a = a * a;
		b >>= 1;
	}
	return res;
}

pii work(matrix a,vector<ll> & e )
{
ll ansa=0,ansb=0;

for(int j=0;j<LN;j++)
       ansa=add(ansa,mult(a.jt[0][j],e[j])),ansb=add(ansb,mult(a.jt[10][j],e[j]));
    
    return {ansa,ansb};
}

int main()
{
int t;
    FAST;
    cin >> t;
    while(t--)
    {
     ll a,b,i,j,c,d,e,f,g,h,n;   
        
     cin >> a >> b >> c >> d >> e >> f >> g >> h >> n;   
        
     matrix A;   
        
        A.reset();
        
     A.jt[0][a-1]+=1;
     A.jt[0][10+b-1]+=1;
     A.jt[0][10+c-1]+=1;
     
     A.jt[0][20]+=d;
     A.jt[0][21]+=d;
        
     A.jt[10][10+e-1]+=1;
     A.jt[10][f-1]+=1;
     A.jt[10][g-1]+=1;
     
     A.jt[10][22]+=h;
     A.jt[10][23]+=h;
        
    for(i=1;i<=9;i++) A.jt[i][i-1]=1;    
    for(i=11;i<=19;i++) A.jt[i][i-1]=1;
        
    A.jt[20][20]=d;
    A.jt[20][21]=d;
        
    A.jt[21][21]=d;
        
    A.jt[22][22]=h;
    A.jt[22][23]=h;
        
    A.jt[23][23]=h;
        
     
    for(i=0;i<24;i++)
    {
     for(j=0;j<24;j++) cout << A.jt[i][j] << " " ;
        cout << endl;
        }
        
        
        
    matrix temp = bin_pow(A,n);    
        
     vector<ll> vv(23,1);
        
      vv[0]=3;  
      vv[10]=3;
        
      vv[20]=0;
       vv[22]=0; 
        
        
    auto z = work(temp,vv);    
        
      cout << z.first << " " << z.second << "\n";  
        
    }
    
    
    
}


run \| edit \| history \| help	0