fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long MOD=1e9+7;
  5.  
  6.  
  7. vector<vector<long long> > multiply(vector<vector<long long> > a,vector<vector<long long> > b)
  8.  {
  9.  	int i,j,k;
  10.  	int r1=a.size();
  11.  	int r2=b.size();
  12.  	int c1=a[0].size();
  13.  	int c2=b[0].size();
  14.  
  15.  	vector<vector<long long> > c(r1,vector<long long> (c2));
  16.  	for(i=0;i<r1;i++)
  17.  	  {
  18.  	  	for(j=0;j<c2;j++)
  19.  	  	  {
  20.  	  	  	for(k=0;k<r2;k++)
  21.  	  	  	  {
  22.  	  	  	  	c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
  23.  	  	  	  }
  24.  	  	  }
  25.  	  }
  26.  	return c;
  27.  }
  28.  
  29. vector<vector<long long> > pow(vector<vector<long long> > a,long long n)
  30.   {
  31.   	if(n==0)
  32.   	  {
  33.   	  	//will not go here;
  34.   	  	return a;
  35.   	  }
  36.   	if(n==1)
  37.   	  return a;
  38.  
  39.   	vector<vector<long long> > b=pow(a,n/2);
  40.   	b=multiply(b,b);
  41.   	if(n%2)
  42.   	  b=multiply(a,b);
  43.   	return b;
  44.   }
  45. long long eval(long long n,vector<vector<long long> > a,vector<vector<long long> > b)
  46.  {
  47.  	if(n==0)
  48.    	  return 1;
  49.    	else
  50.    	  {
  51.    	  	vector<vector<long long> > d=pow(a,n);
  52.    	  	d=multiply(d,b);
  53.    	  	long long sum=0;
  54.    	  	for(int i=0;i<d.size();i++)
  55.    	  	  sum+=d[i][0];
  56.    	  	return sum%MOD;
  57.    	  }
  58.  }
  59.  
  60.  
  61. long long solve()
  62. {
  63. 	int M,x,y,sz,c=0;
  64. 	cin>>M;
  65. 	cin>>x>>y;
  66. 	sz=(M+1)/2;
  67. 	int mat[25][25]={{0}};
  68. 	int count=(sz*(sz+1))/2;
  69. 	int i,j;
  70. 	for(i=1;i<=sz;i++) 
  71. 	{
  72. 		for(j=1;j<=i;j++) 
  73. 		  {
  74. 		  	mat[i][j]=c++;
  75. 		  }
  76. 	}
  77.    	for(i=1;i<=sz;i++) 
  78. 	{
  79. 		for(j=i+1;j<=sz;j++) 
  80. 		  {
  81. 		  	mat[i][j]=mat[j][i];
  82. 		  }
  83. 	}
  84. 	for(i=1;i<=sz;i++)
  85. 	 {
  86. 	 	for(j=sz+1;j<=M;j++)
  87. 	 	 {
  88. 	 	 	mat[i][j]=mat[i][M+1-j];
  89. 	 	 }
  90. 	 }
  91.  
  92. 	for(i=sz+1;i<=M;i++)
  93. 	 {
  94. 	 	for(j=1;j<=M;j++)
  95. 	 	 {
  96. 	 	 	mat[i][j]=mat[M+1-i][j];
  97. 	 	 }
  98. 	 }
  99. 	 /*cout<<"Matrix\n";
  100. 	 for(i=1;i<=M;i++)
  101. 	  {
  102. 	  	for(j=1;j<=M;j++)
  103. 	  	  cout<<mat[i][j]<<" ";
  104. 	  	cout<<endl;
  105. 	  }
  106. 	  cout<<endl;
  107.    */
  108.    vector<vector<long long> > a(count,vector<long long > (count));
  109.    vector<vector<long long> > b(count,vector<long long> (1));
  110.  
  111.    b[mat[x][y]][0]=1;
  112.    vector<pair<int,int> > ar(8);
  113.    c=0;
  114.    int all[3]={-1,1,0};
  115.    for(int i=0;i<3;i++)
  116.     {
  117.     	for(int j=0;j<3;j++)
  118.     	  {
  119.     	  	if(all[i]==all[j] && all[i]==0)
  120.     	  	  continue;
  121.  
  122.     	  	 ar[c++]=make_pair(all[i],all[j]);
  123.     	  }
  124.     }
  125.   // for(int i=0;i<8;i++)
  126.     // cout<<ar[i].first<<" "<<ar[i].second<<endl;
  127.     c=0;
  128.    for(int i=1;i<=sz;i++)
  129.     {
  130.     	for(int j=1;j<=i;j++)
  131.     	  {
  132.     	  	for(int k=0;k<8;k++)
  133.     	  	 {
  134.     	  	 	x=i+ar[k].first;
  135.     	  	 	y=j+ar[k].second;
  136.     	  	 	if(x>=1 && y>=1 && x<=M && y<=M)
  137.     	  	 	   a[mat[x][y]][c]++;
  138.  
  139.     	  	 }
  140.     	  	c++;
  141.     	  }
  142.     }
  143.    /*
  144.    for(i=0;i<a.size();i++)
  145. 	  {
  146. 	  	for(j=0;j<a[0].size();j++)
  147. 	  	  cout<<a[i][j]<<" ";
  148. 	  	cout<<endl;
  149. 	  }
  150.    for(i=0;i<b.size();i++)
  151. 	  {
  152. 	  	for(j=0;j<b[0].size();j++)
  153. 	  	  cout<<b[i][j]<<" ";
  154. 	  	cout<<endl;
  155. 	  }
  156.    */
  157.    int N;
  158.    cin>>N;
  159.    //cout<<"\nAns=";
  160.    return eval(N,a,b);
  161. }
  162.  
  163. int main()
  164. { //cout<<"MOD "<<MOD<<endl;
  165. freopen("in09.txt","r",stdin);
  166. //freopen("out09.txt","w",stdout);
  167. 	int t;
  168. 	cin>>t;
  169. 	while(t--)
  170. 	 {
  171. 	 	cout<<solve()<<endl;
  172.  
  173. 	 }
  174. }
  175.  
Runtime error #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
2
4
1 1
1
4
2 2
1
stdout
copy 
Standard output is empty
https://ideone.com/nlykwg
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!