fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3.  
  4. typedef long long ll ;
  5.  
  6. ll m , x , y , n ;
  7. ll MOD = 1e9+7 ;
  8.  
  9. void create_sym_matrix( vector< vector<ll> > &sym_matrix , ll len ) {
  10.  
  11. 	//cout << "creating symmetric matrix" << endl ;
  12. 	int counter = 0 ;
  13.  
  14. 	//marking relevent cells with unique numbers...
  15. 	for( int i = 1 ; i <= len ; i++ ) 
  16. 		for( int j = 1 ; j <= i ; j++ ) 
  17. 			sym_matrix[i][j] = counter++ ;
  18.  
  19. 	//copying remaining half as symmetry suggests that...
  20. 	for( int i = 1 ; i <= len ; i++ )
  21. 		for( int j = i+1 ; j <= len ; j++ ) 
  22. 			sym_matrix[i][j] = sym_matrix[j][i] ;
  23.  
  24. 	for( int i = 1 ; i <= len ; i++ )
  25. 		for( int j = len+1 ; j <= m ; j++ )
  26. 			sym_matrix[i][j] = sym_matrix[i][m-j+1] ;
  27.  
  28. 	for( int i = len+1 ; i <= m ; i++ )
  29. 		for( int j = 1 ; j <= m ; j++ )
  30. 			sym_matrix[i][j] = sym_matrix[m-i+1][j] ;
  31.  
  32. 	//cout << "created symmetric matrix" << endl ;
  33. 	//for( int i = 1 ; i <= m ; i++ ) {for( int j = 1 ; j <= m ; j++ ) cout << sym_matrix[i][j] << " " ; cout << endl ;	}
  34.  
  35. }
  36.  
  37. void set_answer_matrix( vector< vector< ll > > &answer_matrix , vector< vector< ll > > sym_matrix , int len ) {
  38.  
  39. 	//cout << "setting answer matrix" << endl ;
  40. 	int a , b , column = 0 ;
  41. 	for( int i = 1 ; i <= len ; i++ ) 
  42. 		for( int j = 1 ; j <= i ; j++ ) {
  43. 			for( int k = -1 ; k <= 1 ; k++ ) 
  44. 				for( int l = -1 ; l <= 1 ; l++ ){
  45. 					if( !k && !l ) ;
  46. 					else {
  47. 						a = i+k ; b = j+l ;
  48.  
  49. 						if( a < 1 || a > m || b < 1 || b > m ) ;
  50. 						else {
  51. 							//cout << a << " , " << b << " , sm: " << sym_matrix[a][b] << " , cl: " << column << endl ;	
  52. 							answer_matrix[ sym_matrix[a][b] ][column]++ ;
  53. 						}
  54. 					}
  55. 				}
  56. 			column++ ;
  57. 			}
  58. 	//cout << "set answer matrix" << endl ;
  59. 	//for( int i = 0 ; i < column ; i++ ) {for( int j = 0 ; j < column ; j++ ) cout << answer_matrix[i][j] << " " ; cout << endl ;	}
  60. }
  61.  
  62. vector< vector< ll > > multiply(vector< vector< ll > > a , vector< vector< ll > > b)
  63.  {
  64.  	int i,j,k;
  65.  	int r1=a.size() , r2=b.size();
  66.  	int c1=a[0].size() , c2=b[0].size();
  67.  
  68.  	vector< vector< ll > > c(r1 , vector< ll >(c2) ) ;
  69.  	for(i=0;i<r1;i++)
  70.  	  {
  71.  	  	for(j=0;j<c2;j++)
  72.  	  	  {
  73.  	  	  	for(k=0;k<r2;k++)
  74.  	  	  	  {
  75.  	  	  	  	c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
  76.  	  	  	  }
  77.  	  	  }
  78.  	  }
  79.  	return c;
  80.  }
  81.  
  82. vector< vector< ll > > power( vector< vector< ll > > a, ll n)
  83.   {
  84.  
  85.   	if( n==1 )
  86.   	  return a;
  87.  
  88.   	vector< vector< ll > > b=power(a,n/2);
  89.   	b=multiply(b,b);
  90.   	if(n&1)
  91.   	  b=multiply(a,b);
  92.   	return b;
  93.   }
  94.  
  95.  
  96. ll calculate_answer( ll n , vector< vector< ll > > answer_matrix , vector< vector< ll > >  sym_matrix )
  97.  {
  98.    	  	vector< vector< ll > > resultant_matrix =power( answer_matrix , n );
  99.  
  100.    	  	ll sum=0;
  101.    	  	for(int i=0 ; i< resultant_matrix.size() ; i++)
  102.    	  	  sum+=resultant_matrix[i][ sym_matrix[x][y] ];
  103.    	  	return sum%MOD;
  104.  
  105.  }
  106.  
  107.  
  108. typedef long long ll ;
  109. int main() {
  110.  
  111. 	int t ;
  112. 	cin >> t ;
  113.  
  114. 	while( t-- ) {
  115.  
  116.  
  117. 		//input taken...
  118. 		cin >> m >> x >> y >> n ;
  119. 		assert( 1 <= m <= 20 ) ;
  120. 		assert( 1 <= x <= m && 1 <= y <= m ) ;
  121. 		assert( 1 <= n <= 1e9 ) ;
  122.  
  123. 		ll len = (m+1)>>1 ;
  124. 		ll moves = len*(len+1)/2 ;
  125. 		vector< vector< ll > > sym_matrix(m+1, vector<ll>(m+1) ) ;
  126. 		create_sym_matrix( sym_matrix , len);
  127.  
  128. 		vector< vector< ll > > answer_matrix( moves , vector< ll >(moves) ) ;
  129.  
  130. 		set_answer_matrix( answer_matrix , sym_matrix , len ) ;		
  131.  
  132. 		ll answer = calculate_answer( n , answer_matrix , sym_matrix ) ;
  133.  
  134. 		assert( 0 <= answer < 1e9-1 ) ;
  135. 		cout << answer << endl ;
  136.  	}
  137. 	return 0 ;
  138. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
3
4
1 1
1
4
2 2
1
4
1 1
2
stdout
copy 
3
8
18
https://ideone.com/QDvgrX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!