fork download
  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
stdin
3
0 1 0
0 0 1
1 0 0
0
stdout
Standard output is empty