fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*==================!!-Code-Starts-From-Here-!!==================*/
  5.  
  6. const int N = 512,B=300;
  7. int dp[33][65][B][N]={};  // dp[k][m][b] -> Preprocessed A^(K)'s , m'th group , b'th index
  8. int AK[33][N][N]={};  // AK[k] -> K-th power of A
  9. int A[N][N];  // A -> original matrix
  10. int ans[N]; // Single row to calculate answer
  11. int temp[N];
  12. int n,m,t; // n -> matrix dimension, m -> number of groups, t -> number of row's/coloumn's per group
  13. vector<int> bits; // -> selection of subsets [1 at a time, 2 at a time ,... t at a time]
  14.  
  15. bool cmp(int a,int b) { // sort by number of set bits accending
  16. 	if(__builtin_popcount(a) == __builtin_popcount(b))
  17. 		return a < b;
  18. 	return __builtin_popcount(a) < __builtin_popcount(b);
  19. }
  20.  
  21. void preProcessAK(int k) { // Preprocess A^(K) K={0,1,2,4,8,....}
  22. 	for(int g=0;g<m;g++) {
  23. 		for(int b=0;b<bits.size();b++) {
  24. 			int rr;
  25. 			for(rr=0;(bits[b]&(1<<rr))==0;rr++); // find least significant bit
  26. 			for(int cc=0;cc<n;cc++) {
  27. 				dp[k][g][bits[b]][cc] = dp[k][g][bits[b]][cc] || dp[k][g][bits[b]^(1<<rr)][cc] ||  AK[k][(g*t)+rr][cc];
  28. 				// dp[bit-index][col] = dp[bit-index ^ lsb][col] || A[lsb + offset of group][col]
  29. 			}
  30. 		}
  31. 	}
  32.  
  33. 	int left=n%t; // group with less than t-rows
  34. 	for(int b=0;b<bits.size();b++) {
  35. 		int msb = 32 - __builtin_clz(bits[b]);
  36. 		if(msb > left) continue;
  37. 		int rr;
  38. 		for(rr=0;(bits[b]&(1<<rr))==0;rr++); // find least significant bit
  39. 		for(int cc=0;cc<n;cc++) {
  40. 			dp[k][m][bits[b]][cc] = dp[k][m][bits[b]][cc] || dp[k][m][bits[b]^(1<<rr)][cc] || AK[k][(m*t)+rr][cc];
  41. 		}
  42. 	}
  43. 	return;
  44. }
  45.  
  46. void Init(int p) { // Initialization to calculate all A^(k)'s and preprocess them
  47. 	t = log2(n); // division of  'n' into 'm' groups of size 't'
  48. 	m = n/t;
  49. 	for(int i=1;i<(1<<t);i++) { // find all 2^(t)-1 combinations and sort by N(set-bits)
  50. 		bits.push_back(i);
  51. 	}
  52. 	sort(bits.begin(),bits.end(),cmp);
  53.  
  54. 	for(int i=0;i<n;i++) { // Preprocess Initial Matrix A^(0) = A
  55. 		for(int j=0;j<n;j++) {
  56. 			AK[0][i][j] = A[i][j];
  57. 		}
  58. 	}
  59. 	preProcessAK(0);
  60.  
  61. 	for(int k=1;k<p;k++) { // Power - k
  62. 		for(int rr=0;rr<n;rr++) { // Row - rr
  63. 			for(int g=0;g<m;g++) { // Group - g
  64. 				int b=0;
  65. 				for(int cc=0;cc<t;cc++) { // bit-index - b
  66. 					b = b | (AK[k-1][rr][(g*t)+cc]<<cc);
  67. 				}
  68. 				for(int cc=0;cc<n;cc++) {
  69. 					AK[k][rr][cc] = AK[k][rr][cc] || dp[k-1][g][b][cc];
  70. 					// A^(k) [row][col] = A^(k) [row][col] or DP(A^(k-1))[group][bit-index][col];
  71. 				}
  72. 			}
  73.  
  74. 			int left = n%t; // group with less than 't' bits
  75. 			int b=0;
  76. 			for(int cc=0;cc<left;cc++) {
  77. 				b = b | (AK[k-1][rr][(m*t)+cc]<<cc);
  78. 			}
  79. 			for(int cc=0;cc<n;cc++) {
  80. 				AK[k][rr][cc] = AK[k][rr][cc] || dp[k-1][m][b][cc];
  81. 			}
  82. 		}
  83. 		preProcessAK(k);
  84. 	}
  85. }
  86.  
  87. void solve(int rr,int p) { // row-rr , power-p of A needed
  88. 	memset(ans,0,sizeof(ans));
  89. 	int k=0; // power-k of A used now {0,1,2,4,8,....}
  90. 	bool ok=false;
  91. 	while(p) {
  92. 		if((p&1)) { // current power-k is needed
  93. 			if(!ok) { // first - needed ans[col] = A^(K)[row][col]
  94. 				for(int cc=0;cc<n;cc++) {
  95. 					ans[cc]=AK[k][rr][cc];
  96. 				}
  97. 				k++;
  98. 				p=p>>1;
  99. 				ok=true;
  100. 				continue;
  101. 			}
  102.  
  103. 			for(int cc=0;cc<n;cc++) { // from second need of A^(k)
  104. 				temp[cc]=ans[cc];
  105. 				ans[cc]=0;
  106. 			}
  107. 			for(int g=0;g<m;g++) { // group - g
  108. 				int b=0;
  109. 				for(int cc=0;cc<t;cc++) { // bit-index - b
  110. 					b = b | (temp[(g*t)+cc]<<cc);
  111. 				}
  112. 				for(int cc=0;cc<n;cc++) {
  113. 					ans[cc] = ans[cc] || dp[k][g][b][cc];
  114. 					// ans[col] = ans[col] or DP(A^(K))[group][bit-index][col]
  115. 				}
  116. 			}
  117.  
  118. 			int left = n%t; // group with less than t - rows/cols
  119. 			int b=0;
  120. 			for(int cc=0;cc<left;cc++) {
  121. 				b = b | (temp[(m*t)+cc]<<cc);
  122. 			}
  123. 			for(int cc=0;cc<n;cc++) {
  124. 				ans[cc] = ans[cc] || dp[k][m][b][cc];
  125. 			}
  126. 		}
  127.  
  128. 		p=p>>1;
  129. 		k++;
  130. 	}
  131. }
  132. int main() {
  133. 	scanf("%d",&n); // get - dimension of square matrix
  134. 	for(int rr=0;rr<n;rr++) { // and also matrix
  135. 		for(int cc=0;cc<n;cc++) {
  136. 			scanf("%d",&A[rr][cc]);
  137. 		}
  138. 	}
  139.  
  140. 	if(n==1) { // special case dimension - 1x1
  141. 		int test,k,rr;
  142. 		scanf("%d",&test);
  143. 		while(test--) {
  144. 			scanf("%d",&k);scanf("%d",&rr);
  145. 			if(k==0 || (A[0][0]==1)) {
  146. 				puts("1\n1");
  147. 			} else {
  148. 				puts("0\n-1");
  149. 			}
  150. 		}
  151. 		return 0;
  152. 	}
  153.  
  154. 	Init(32); // Precompute - all DP[A^(K)] k:{0,1,2,...31}
  155.  
  156. 	int test;
  157. 	scanf("%d",&test);
  158.  
  159. 	while(test--) {
  160. 		int k,rr;
  161. 		scanf("%d",&k);scanf("%d",&rr);
  162. 		rr--;
  163. 		if(k==0) { // Base-case
  164. 			printf("1\n%d\n",rr+1);
  165. 			continue;
  166. 		}
  167.  
  168. 		solve(rr,k); // solve for row -rr of A^(k)
  169. 		vector<int> val;
  170. 		for(int cc=0;cc<n;cc++) {
  171. 			if(ans[cc]==1) val.push_back(cc+1);
  172. 		}
  173.  
  174. 		printf("%d\n",(int)val.size());
  175. 		if(val.size()==0) printf("-1");
  176. 		for(int cc=0;cc<val.size();cc++) {
  177. 			printf("%d ",val[cc]);
  178. 		}
  179. 		printf("\n");
  180. 	}
  181. 	return 0;
  182. }
  183.  
  184. /*=======================!!-End-Of-Code-!!=======================*/
  185.  
Success #stdin #stdout 0s 1325056KB
comments (?)
stdin
copy 
3
0 1 0
0 0 1
1 0 0
0
stdout
copy 
Standard output is empty
https://ideone.com/kG7j9u
language:
C++14 (gcc 8.3)
created:
7 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!