#include using namespace std; #define mp(a,b) make_pair(a,b) #define ff first #define setp(x) setprecision(x)<-1; i--){ has*=has; has%=modulo; if(b&((lli)1< > arr; int n, m; Matrix(){} Matrix(int n,int m, int val){ // initialize dioganal to 1, or 0 this->n = n; this->m = m; arr.resize(n); fori(n) arr[i].resize(m); fori(n){ forj(m) arr[i][j] = 0; arr[i][i] = val; } } Matrix(vector > arr){ this->arr = arr; n = arr.size(); m = arr[0].size(); } Matrix Multiply(Matrix& A){ int n1 = A.n , m1 = A.m; assert(m==n1); vector > lz; lz.resize(n); fori(n){ lz[i].resize(m1); forj(m1) lz[i][j] = 0; } fori(n) for(int j1=0; j1 > (B.n, vector (B.n,0))); // B.m should be equal to B.n fori(B.n) start.arr[i][i] = 1; for(int i=Max_pow-1; i>-1; i--) if((1< > minions){ Matrix transitions[25]; // transition matrix from time i to time i+1 transitions[0] = Matrix(vector >(n*m, vector(n*m,0))); fori(n*m) transitions[0].arr[i][i] = 1; for(int time = 1; time<=24; ++time){ int occupied[n][m] = {}; fori(k){ for(int j=0; j<2; j++){ minions[i][j] += minions[i][j+4]; if(minions[i][j]==minions[i][j+2]){ minions[i][j+4] = -minions[i][j+4]; swap(minions[i][j+2],minions[i][j+6]); } } occupied[minions[i][0]][minions[i][1]] = 1; } Matrix mat(vector >(n*m, vector(n*m,0))); fori(n) forj(m) fork(n) forl(m){ int dif = fabs(i-k) + fabs(j-l); if(dif<=r && !occupied[k][l]) mat.arr[i*m+j][k*m+l] = 1; } fori(n*m){ lli s = 0; forj(n*m) s+=mat.arr[i][j]; s = pow_mod(s,modulo-2); forj(n*m) if(mat.arr[i][j] == 1) mat.arr[i][j] = s; } transitions[time] = transitions[time-1].Multiply(mat); } int nece = t/24; Matrix ans = exponentiate(transitions[24],nece); ans = ans.Multiply(transitions[t-nece*24]); return ans; } void deal(){ int n,m,r1,r2,k,t; cin>>n>>m>>r1>>r2>>k>>t; vector > minions; minions.resize(k); fori(k){ minions[i].resize(8); forj(4) cin>>minions[i][j]; minions[i][4] = (minions[i][2]-minions[i][0]); minions[i][5] = (minions[i][3]-minions[i][1]); forj(2) minions[i][j+6] = minions[i][j]; for(int j=4; j<6; j++) if(minions[i][j]!=0) minions[i][j]/=fabs(minions[i][j]); } Matrix ans1 = answer(r1,n,m,k,t,minions), ans2 = answer(r2,n,m,k,t,minions); // display(ans1); // display(ans2); lli p = 0; fori(n*m){ p+=ans1.arr[0][i]*ans2.arr[n*m-1][i]; p%=modulo; } cout<