API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
116
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.80 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long llint;
  6.  
  7. const int MAXN = (1 << 12) + 5;
  8.  
  9. int n, w, m, len, sd, gpot, flg, dens;
  10. bitset <(1 << 12) + 10> bt[400];
  11. bitset <150> mask[(1 << 12) + 10];
  12. int prr[15] = {0, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5};
  13. int p[MAXN], g[MAXN][MAXN], dd[30][30], sjeme[30][30], dd2[30][30], sjeme2[30][30], ro[30][30];
  14. llint rnd = 1, ca = 31337, cb = 24253453, mod = 1000000007;
  15.  
  16. llint rnd_br () {
  17.     llint res = rnd;
  18.     rnd = (rnd * ca + cb) % mod;
  19.     return res;
  20. }
  21.  
  22. llint rnd_shuffle () {
  23.     for (int i=n; i>1; i--) {
  24.         swap(p[i], p[rnd_br() % i + 1]);
  25.     }
  26. }
  27.  
  28. void precompute() {
  29. dd[1][2] = 5; sjeme[1][2] = 1;
  30. dd[1][3] = 7; sjeme[1][3] = 1;
  31. dd[1][4] = 9; sjeme[1][4] = 1;
  32. dd[1][5] = 11; sjeme[1][5] = 1;
  33. dd[1][6] = 13; sjeme[1][6] = 1;
  34. dd[1][7] = 15; sjeme[1][7] = 1;
  35. dd[1][8] = 17; sjeme[1][8] = 1;
  36. dd[1][9] = 19; sjeme[1][9] = 1;
  37. dd[1][10] = 21; sjeme[1][10] = 1;
  38. dd[1][11] = 23; sjeme[1][11] = 1;
  39. dd[1][12] = 25; sjeme[1][12] = 1;
  40. dd[1][13] = 27; sjeme[1][13] = 1;
  41. dd[1][14] = 29; sjeme[1][14] = 1;
  42. dd[1][15] = 31; sjeme[1][15] = 1;
  43. dd[1][16] = 33; sjeme[1][16] = 1;
  44. dd[2][2] = 8; sjeme[2][2] = 4;
  45. dd[2][3] = 11; sjeme[2][3] = 2;
  46. dd[2][4] = 14; sjeme[2][4] = 2;
  47. dd[2][5] = 17; sjeme[2][5] = 10;
  48. dd[2][6] = 20; sjeme[2][6] = 16;
  49. dd[2][7] = 23; sjeme[2][7] = 10;
  50. dd[2][8] = 26; sjeme[2][8] = 4;
  51. dd[2][9] = 29; sjeme[2][9] = 4;
  52. dd[2][10] = 32; sjeme[2][10] = 29;
  53. dd[2][11] = 35; sjeme[2][11] = 2;
  54. dd[2][12] = 38; sjeme[2][12] = 2;
  55. dd[2][13] = 41; sjeme[2][13] = 2;
  56. dd[2][14] = 44; sjeme[2][14] = 39;
  57. dd[2][15] = 47; sjeme[2][15] = 19;
  58. dd[2][16] = 50; sjeme[2][16] = 2;
  59. dd[3][2] = 11; sjeme[3][2] = 129;
  60. dd[3][3] = 15; sjeme[3][3] = 377;
  61. dd[3][4] = 19; sjeme[3][4] = 42;
  62. dd[3][5] = 23; sjeme[3][5] = 446;
  63. dd[3][6] = 27; sjeme[3][6] = 55;
  64. dd[3][7] = 30; sjeme[3][7] = 312;
  65. dd[3][8] = 34; sjeme[3][8] = 213;
  66. dd[3][9] = 39; sjeme[3][9] = 55;
  67. dd[3][10] = 41; sjeme[3][10] = 213;
  68. dd[3][11] = 46; sjeme[3][11] = 211;
  69. dd[3][12] = 50; sjeme[3][12] = 40;
  70. dd[3][13] = 53; sjeme[3][13] = 187;
  71. dd[3][14] = 57; sjeme[3][14] = 255;
  72. dd[3][15] = 61; sjeme[3][15] = 18;
  73. dd[3][16] = 64; sjeme[3][16] = 258;
  74. dd[4][2] = 15; sjeme[4][2] = 42;
  75. dd[4][3] = 19; sjeme[4][3] = 410;
  76. dd[4][4] = 24; sjeme[4][4] = 338;
  77. dd[4][5] = 28; sjeme[4][5] = 236;
  78. dd[4][6] = 33; sjeme[4][6] = 236;
  79. dd[4][7] = 37; sjeme[4][7] = 494;
  80. dd[4][8] = 42; sjeme[4][8] = 185;
  81. dd[4][9] = 47; sjeme[4][9] = 28;
  82. dd[4][10] = 50; sjeme[4][10] = 28;
  83. dd[4][11] = 54; sjeme[4][11] = 149;
  84. dd[4][12] = 58; sjeme[4][12] = 319;
  85. dd[4][13] = 62; sjeme[4][13] = 500;
  86. dd[4][14] = 66; sjeme[4][14] = 500;
  87. dd[4][15] = 70; sjeme[4][15] = 500;
  88. dd[4][16] = 75; sjeme[4][16] = 310;
  89. dd[5][2] = 18; sjeme[5][2] = 303;
  90. dd[5][3] = 23; sjeme[5][3] = 394;
  91. dd[5][4] = 28; sjeme[5][4] = 11;
  92. dd[5][5] = 33; sjeme[5][5] = 11;
  93. dd[5][6] = 38; sjeme[5][6] = 66;
  94. dd[5][7] = 43; sjeme[5][7] = 97;
  95. dd[5][8] = 47; sjeme[5][8] = 113;
  96. dd[5][9] = 52; sjeme[5][9] = 21;
  97. dd[5][10] = 56; sjeme[5][10] = 415;
  98. dd[5][11] = 62; sjeme[5][11] = 23;
  99. dd[5][12] = 66; sjeme[5][12] = 94;
  100. dd[5][13] = 70; sjeme[5][13] = 225;
  101. dd[5][14] = 74; sjeme[5][14] = 225;
  102. dd[5][15] = 78; sjeme[5][15] = 225;
  103. dd[5][16] = 83; sjeme[5][16] = 381;
  104. dd[6][2] = 21; sjeme[6][2] = 39;
  105. dd[6][3] = 27; sjeme[6][3] = 129;
  106. dd[6][4] = 32; sjeme[6][4] = 59;
  107. dd[6][5] = 37; sjeme[6][5] = 59;
  108. dd[6][6] = 43; sjeme[6][6] = 37;
  109. dd[6][7] = 47; sjeme[6][7] = 305;
  110. dd[6][8] = 52; sjeme[6][8] = 248;
  111. dd[6][9] = 57; sjeme[6][9] = 59;
  112. dd[6][10] = 62; sjeme[6][10] = 38;
  113. dd[6][11] = 67; sjeme[6][11] = 168;
  114. dd[6][12] = 72; sjeme[6][12] = 262;
  115. dd[6][13] = 76; sjeme[6][13] = 182;
  116. dd[6][14] = 81; sjeme[6][14] = 107;
  117. dd[6][15] = 85; sjeme[6][15] = 343;
  118. dd[6][16] = 89; sjeme[6][16] = 107;
  119. dd[7][2] = 24; sjeme[7][2] = 311;
  120. dd[7][3] = 30; sjeme[7][3] = 16;
  121. dd[7][4] = 35; sjeme[7][4] = 1;
  122. dd[7][5] = 40; sjeme[7][5] = 247;
  123. dd[7][6] = 46; sjeme[7][6] = 160;
  124. dd[7][7] = 51; sjeme[7][7] = 38;
  125. dd[7][8] = 56; sjeme[7][8] = 251;
  126. dd[7][9] = 61; sjeme[7][9] = 123;
  127. dd[7][10] = 66; sjeme[7][10] = 251;
  128. dd[7][11] = 71; sjeme[7][11] = 6;
  129. dd[7][12] = 76; sjeme[7][12] = 202;
  130. dd[7][13] = 80; sjeme[7][13] = 54;
  131. dd[7][14] = 85; sjeme[7][14] = 103;
  132. dd[7][15] = 91; sjeme[7][15] = 2;
  133. dd[7][16] = 95; sjeme[7][16] = 85;
  134. dd[8][2] = 27; sjeme[8][2] = 39;
  135. dd[8][3] = 33; sjeme[8][3] = 153;
  136. dd[8][4] = 39; sjeme[8][4] = 77;
  137. dd[8][5] = 44; sjeme[8][5] = 50;
  138. dd[8][6] = 50; sjeme[8][6] = 210;
  139. dd[8][7] = 55; sjeme[8][7] = 242;
  140. dd[8][8] = 60; sjeme[8][8] = 142;
  141. dd[8][9] = 66; sjeme[8][9] = 226;
  142. dd[8][10] = 71; sjeme[8][10] = 10;
  143. dd[8][11] = 74; sjeme[8][11] = 400;
  144. dd[8][12] = 80; sjeme[8][12] = 336;
  145. dd[8][13] = 86; sjeme[8][13] = 229;
  146. dd[8][14] = 91; sjeme[8][14] = 4;
  147. dd[8][15] = 95; sjeme[8][15] = 206;
  148. dd[8][16] = 100; sjeme[8][16] = 159;
  149. dd[9][2] = 30; sjeme[9][2] = 84;
  150. dd[9][3] = 35; sjeme[9][3] = 451;
  151. dd[9][4] = 41; sjeme[9][4] = 28;
  152. dd[9][5] = 47; sjeme[9][5] = 171;
  153. dd[9][6] = 52; sjeme[9][6] = 118;
  154. dd[9][7] = 58; sjeme[9][7] = 33;
  155. dd[9][8] = 65; sjeme[9][8] = 24;
  156. dd[9][9] = 68; sjeme[9][9] = 181;
  157. dd[9][10] = 75; sjeme[9][10] = 25;
  158. dd[9][11] = 80; sjeme[9][11] = 58;
  159. dd[9][12] = 85; sjeme[9][12] = 365;
  160. dd[9][13] = 89; sjeme[9][13] = 101;
  161. dd[9][14] = 94; sjeme[9][14] = 243;
  162. dd[9][15] = 99; sjeme[9][15] = 342;
  163. dd[9][16] = 105; sjeme[9][16] = 50;
  164. dd[10][2] = 32; sjeme[10][2] = 115;
  165. dd[10][3] = 39; sjeme[10][3] = 141;
  166. dd[10][4] = 45; sjeme[10][4] = 27;
  167. dd[10][5] = 51; sjeme[10][5] = 82;
  168. dd[10][6] = 56; sjeme[10][6] = 39;
  169. dd[10][7] = 61; sjeme[10][7] = 186;
  170. dd[10][8] = 67; sjeme[10][8] = 175;
  171. dd[10][9] = 73; sjeme[10][9] = 72;
  172. dd[10][10] = 78; sjeme[10][10] = 41;
  173. dd[10][11] = 84; sjeme[10][11] = 9;
  174. dd[10][12] = 88; sjeme[10][12] = 301;
  175. dd[10][13] = 94; sjeme[10][13] = 9;
  176. dd[10][14] = 99; sjeme[10][14] = 49;
  177. dd[10][15] = 104; sjeme[10][15] = 116;
  178. dd[10][16] = 109; sjeme[10][16] = 34;
  179. dd[11][2] = 34; sjeme[11][2] = 186;
  180. dd[11][3] = 41; sjeme[11][3] = 349;
  181. dd[11][4] = 47; sjeme[11][4] = 214;
  182. dd[11][5] = 53; sjeme[11][5] = 482;
  183. dd[11][6] = 60; sjeme[11][6] = 27;
  184. dd[11][7] = 65; sjeme[11][7] = 40;
  185. dd[11][8] = 70; sjeme[11][8] = 69;
  186. dd[11][9] = 76; sjeme[11][9] = 63;
  187. dd[11][10] = 81; sjeme[11][10] = 157;
  188. dd[11][11] = 87; sjeme[11][11] = 82;
  189. dd[11][12] = 92; sjeme[11][12] = 128;
  190. dd[11][13] = 97; sjeme[11][13] = 354;
  191. dd[11][14] = 102; sjeme[11][14] = 223;
  192. dd[11][15] = 106; sjeme[11][15] = 359;
  193. dd[11][16] = 112; sjeme[11][16] = 145;
  194. dd[12][2] = 36; sjeme[12][2] = 132;
  195. dd[12][3] = 43; sjeme[12][3] = 273;
  196. dd[12][4] = 50; sjeme[12][4] = 288;
  197. dd[12][5] = 56; sjeme[12][5] = 129;
  198. dd[12][6] = 62; sjeme[12][6] = 82;
  199. dd[12][7] = 67; sjeme[12][7] = 339;
  200. dd[12][8] = 74; sjeme[12][8] = 4;
  201. dd[12][9] = 79; sjeme[12][9] = 403;
  202. dd[12][10] = 84; sjeme[12][10] = 404;
  203. dd[12][11] = 89; sjeme[12][11] = 242;
  204. dd[12][12] = 95; sjeme[12][12] = 211;
  205. dd[12][13] = 100; sjeme[12][13] = 396;
  206. dd[12][14] = 106; sjeme[12][14] = 497;
  207. dd[12][15] = 111; sjeme[12][15] = 81;
  208. dd[12][16] = 117; sjeme[12][16] = 49;
  209. dd2[1][2] = 5; sjeme2[1][2] = 1; ro[1][2] = 15;
  210. dd2[1][3] = 7; sjeme2[1][3] = 1; ro[1][3] = 15;
  211. dd2[1][4] = 9; sjeme2[1][4] = 1; ro[1][4] = 15;
  212. dd2[1][5] = 11; sjeme2[1][5] = 1; ro[1][5] = 15;
  213. dd2[1][6] = 13; sjeme2[1][6] = 1; ro[1][6] = 15;
  214. dd2[1][7] = 15; sjeme2[1][7] = 1; ro[1][7] = 15;
  215. dd2[1][8] = 17; sjeme2[1][8] = 1; ro[1][8] = 15;
  216. dd2[1][9] = 19; sjeme2[1][9] = 1; ro[1][9] = 15;
  217. dd2[1][10] = 21; sjeme2[1][10] = 1; ro[1][10] = 15;
  218. dd2[1][11] = 23; sjeme2[1][11] = 1; ro[1][11] = 15;
  219. dd2[1][12] = 25; sjeme2[1][12] = 1; ro[1][12] = 15;
  220. dd2[1][13] = 27; sjeme2[1][13] = 1; ro[1][13] = 15;
  221. dd2[1][14] = 29; sjeme2[1][14] = 1; ro[1][14] = 15;
  222. dd2[1][15] = 31; sjeme2[1][15] = 1; ro[1][15] = 15;
  223. dd2[1][16] = 33; sjeme2[1][16] = 1; ro[1][16] = 15;
  224. dd2[1][2] = 5; sjeme2[1][2] = 1; ro[1][2] = 15;
  225. dd2[1][3] = 7; sjeme2[1][3] = 1; ro[1][3] = 15;
  226. dd2[1][4] = 9; sjeme2[1][4] = 1; ro[1][4] = 15;
  227. dd2[1][5] = 11; sjeme2[1][5] = 1; ro[1][5] = 15;
  228. dd2[1][6] = 13; sjeme2[1][6] = 1; ro[1][6] = 15;
  229. dd2[1][7] = 15; sjeme2[1][7] = 1; ro[1][7] = 15;
  230. dd2[1][8] = 17; sjeme2[1][8] = 1; ro[1][8] = 15;
  231. dd2[1][9] = 19; sjeme2[1][9] = 1; ro[1][9] = 15;
  232. dd2[1][10] = 21; sjeme2[1][10] = 1; ro[1][10] = 15;
  233. dd2[1][11] = 23; sjeme2[1][11] = 1; ro[1][11] = 15;
  234. dd2[1][12] = 25; sjeme2[1][12] = 1; ro[1][12] = 15;
  235. dd2[1][13] = 27; sjeme2[1][13] = 1; ro[1][13] = 15;
  236. dd2[1][14] = 29; sjeme2[1][14] = 1; ro[1][14] = 15;
  237. dd2[1][15] = 31; sjeme2[1][15] = 1; ro[1][15] = 15;
  238. dd2[1][16] = 33; sjeme2[1][16] = 1; ro[1][16] = 15;
  239. dd2[2][2] = 8; sjeme2[2][2] = 1; ro[2][2] = 16;
  240. dd2[2][3] = 11; sjeme2[2][3] = 1; ro[2][3] = 16;
  241. dd2[2][4] = 14; sjeme2[2][4] = 84; ro[2][4] = 16;
  242. dd2[2][5] = 17; sjeme2[2][5] = 283; ro[2][5] = 16;
  243. dd2[2][6] = 20; sjeme2[2][6] = 283; ro[2][6] = 18;
  244. dd2[2][7] = 23; sjeme2[2][7] = 283; ro[2][7] = 18;
  245. dd2[2][8] = 27; sjeme2[2][8] = 283; ro[2][8] = 18;
  246. dd2[2][9] = 31; sjeme2[2][9] = 193; ro[2][9] = 16;
  247. dd2[2][10] = 35; sjeme2[2][10] = 84; ro[2][10] = 16;
  248. dd2[2][11] = 38; sjeme2[2][11] = 283; ro[2][11] = 18;
  249. dd2[2][12] = 41; sjeme2[2][12] = 283; ro[2][12] = 18;
  250. dd2[2][13] = 44; sjeme2[2][13] = 283; ro[2][13] = 18;
  251. dd2[2][14] = 48; sjeme2[2][14] = 283; ro[2][14] = 18;
  252. dd2[2][15] = 53; sjeme2[2][15] = 260; ro[2][15] = 18;
  253. dd2[2][16] = 56; sjeme2[2][16] = 260; ro[2][16] = 18;
  254. dd2[3][2] = 10; sjeme2[3][2] = 6; ro[3][2] = 16;
  255. dd2[3][3] = 13; sjeme2[3][3] = 220; ro[3][3] = 16;
  256. dd2[3][4] = 17; sjeme2[3][4] = 87; ro[3][4] = 16;
  257. dd2[3][5] = 20; sjeme2[3][5] = 148; ro[3][5] = 20;
  258. dd2[3][6] = 24; sjeme2[3][6] = 201; ro[3][6] = 20;
  259. dd2[3][7] = 28; sjeme2[3][7] = 260; ro[3][7] = 26;
  260. dd2[3][8] = 32; sjeme2[3][8] = 290; ro[3][8] = 24;
  261. dd2[3][9] = 37; sjeme2[3][9] = 177; ro[3][9] = 16;
  262. dd2[3][10] = 39; sjeme2[3][10] = 260; ro[3][10] = 26;
  263. dd2[3][11] = 44; sjeme2[3][11] = 240; ro[3][11] = 24;
  264. dd2[3][12] = 49; sjeme2[3][12] = 159; ro[3][12] = 16;
  265. dd2[3][13] = 51; sjeme2[3][13] = 159; ro[3][13] = 16;
  266. dd2[3][14] = 55; sjeme2[3][14] = 159; ro[3][14] = 16;
  267. dd2[3][15] = 58; sjeme2[3][15] = 159; ro[3][15] = 16;
  268. dd2[3][16] = 63; sjeme2[3][16] = 159; ro[3][16] = 16;
  269. dd2[4][2] = 11; sjeme2[4][2] = 34; ro[4][2] = 18;
  270. dd2[4][3] = 15; sjeme2[4][3] = 41; ro[4][3] = 19;
  271. dd2[4][4] = 19; sjeme2[4][4] = 231; ro[4][4] = 18;
  272. dd2[4][5] = 23; sjeme2[4][5] = 66; ro[4][5] = 15;
  273. dd2[4][6] = 28; sjeme2[4][6] = 3; ro[4][6] = 16;
  274. dd2[4][7] = 31; sjeme2[4][7] = 136; ro[4][7] = 24;
  275. dd2[4][8] = 36; sjeme2[4][8] = 8; ro[4][8] = 15;
  276. dd2[4][9] = 40; sjeme2[4][9] = 247; ro[4][9] = 15;
  277. dd2[4][10] = 44; sjeme2[4][10] = 300; ro[4][10] = 21;
  278. dd2[4][11] = 48; sjeme2[4][11] = 300; ro[4][11] = 21;
  279. dd2[4][12] = 52; sjeme2[4][12] = 196; ro[4][12] = 26;
  280. dd2[4][13] = 56; sjeme2[4][13] = 81; ro[4][13] = 24;
  281. dd2[4][14] = 60; sjeme2[4][14] = 107; ro[4][14] = 16;
  282. dd2[4][15] = 63; sjeme2[4][15] = 271; ro[4][15] = 18;
  283. dd2[4][16] = 68; sjeme2[4][16] = 81; ro[4][16] = 24;
  284. dd2[5][2] = 13; sjeme2[5][2] = 85; ro[5][2] = 15;
  285. dd2[5][3] = 17; sjeme2[5][3] = 58; ro[5][3] = 15;
  286. dd2[5][4] = 21; sjeme2[5][4] = 207; ro[5][4] = 27;
  287. dd2[5][5] = 26; sjeme2[5][5] = 244; ro[5][5] = 16;
  288. dd2[5][6] = 30; sjeme2[5][6] = 70; ro[5][6] = 15;
  289. dd2[5][7] = 34; sjeme2[5][7] = 15; ro[5][7] = 15;
  290. dd2[5][8] = 38; sjeme2[5][8] = 15; ro[5][8] = 15;
  291. dd2[5][9] = 41; sjeme2[5][9] = 15; ro[5][9] = 15;
  292. dd2[5][10] = 48; sjeme2[5][10] = 15; ro[5][10] = 15;
  293. dd2[5][11] = 52; sjeme2[5][11] = 45; ro[5][11] = 19;
  294. dd2[5][12] = 56; sjeme2[5][12] = 96; ro[5][12] = 15;
  295. dd2[5][13] = 61; sjeme2[5][13] = 76; ro[5][13] = 16;
  296. dd2[5][14] = 65; sjeme2[5][14] = 76; ro[5][14] = 16;
  297. dd2[5][15] = 68; sjeme2[5][15] = 28; ro[5][15] = 20;
  298. dd2[5][16] = 73; sjeme2[5][16] = 16; ro[5][16] = 21;
  299. dd2[6][2] = 15; sjeme2[6][2] = 25; ro[6][2] = 15;
  300. dd2[6][3] = 19; sjeme2[6][3] = 9; ro[6][3] = 19;
  301. dd2[6][4] = 24; sjeme2[6][4] = 77; ro[6][4] = 27;
  302. dd2[6][5] = 28; sjeme2[6][5] = 16; ro[6][5] = 24;
  303. dd2[6][6] = 32; sjeme2[6][6] = 69; ro[6][6] = 25;
  304. dd2[6][7] = 37; sjeme2[6][7] = 93; ro[6][7] = 15;
  305. dd2[6][8] = 42; sjeme2[6][8] = 30; ro[6][8] = 26;
  306. dd2[6][9] = 46; sjeme2[6][9] = 93; ro[6][9] = 15;
  307. dd2[6][10] = 51; sjeme2[6][10] = 99; ro[6][10] = 21;
  308. dd2[6][11] = 56; sjeme2[6][11] = 36; ro[6][11] = 19;
  309. dd2[6][12] = 59; sjeme2[6][12] = 20; ro[6][12] = 17;
  310. dd2[6][13] = 63; sjeme2[6][13] = 15; ro[6][13] = 25;
  311. dd2[6][14] = 68; sjeme2[6][14] = 23; ro[6][14] = 24;
  312. dd2[6][15] = 73; sjeme2[6][15] = 42; ro[6][15] = 19;
  313. dd2[6][16] = 75; sjeme2[6][16] = 34; ro[6][16] = 27;
  314. dd2[7][2] = 16; sjeme2[7][2] = 99; ro[7][2] = 19;
  315. dd2[7][3] = 21; sjeme2[7][3] = 44; ro[7][3] = 17;
  316. dd2[7][4] = 26; sjeme2[7][4] = 24; ro[7][4] = 17;
  317. dd2[7][5] = 30; sjeme2[7][5] = 33; ro[7][5] = 26;
  318. dd2[7][6] = 35; sjeme2[7][6] = 58; ro[7][6] = 16;
  319. dd2[7][7] = 39; sjeme2[7][7] = 48; ro[7][7] = 15;
  320. dd2[7][8] = 44; sjeme2[7][8] = 72; ro[7][8] = 16;
  321. dd2[7][9] = 49; sjeme2[7][9] = 52; ro[7][9] = 19;
  322. dd2[7][10] = 54; sjeme2[7][10] = 17; ro[7][10] = 15;
  323. dd2[7][11] = 58; sjeme2[7][11] = 95; ro[7][11] = 16;
  324. dd2[7][12] = 62; sjeme2[7][12] = 74; ro[7][12] = 18;
  325. dd2[7][13] = 66; sjeme2[7][13] = 77; ro[7][13] = 18;
  326. dd2[7][14] = 71; sjeme2[7][14] = 49; ro[7][14] = 22;
  327. dd2[7][15] = 76; sjeme2[7][15] = 43; ro[7][15] = 19;
  328. dd2[7][16] = 80; sjeme2[7][16] = 44; ro[7][16] = 17;
  329. dd2[8][2] = 17; sjeme2[8][2] = 2; ro[8][2] = 17;
  330. dd2[8][3] = 23; sjeme2[8][3] = 45; ro[8][3] = 18;
  331. dd2[8][4] = 27; sjeme2[8][4] = 53; ro[8][4] = 18;
  332. dd2[8][5] = 32; sjeme2[8][5] = 31; ro[8][5] = 19;
  333. dd2[8][6] = 37; sjeme2[8][6] = 79; ro[8][6] = 24;
  334. dd2[8][7] = 42; sjeme2[8][7] = 70; ro[8][7] = 27;
  335. dd2[8][8] = 46; sjeme2[8][8] = 6; ro[8][8] = 26;
  336. dd2[8][9] = 51; sjeme2[8][9] = 21; ro[8][9] = 20;
  337. dd2[8][10] = 55; sjeme2[8][10] = 21; ro[8][10] = 20;
  338. dd2[8][11] = 59; sjeme2[8][11] = 59; ro[8][11] = 19;
  339. dd2[8][12] = 65; sjeme2[8][12] = 64; ro[8][12] = 20;
  340. dd2[8][13] = 69; sjeme2[8][13] = 39; ro[8][13] = 19;
  341. dd2[8][14] = 74; sjeme2[8][14] = 94; ro[8][14] = 16;
  342. dd2[8][15] = 79; sjeme2[8][15] = 94; ro[8][15] = 16;
  343. dd2[8][16] = 83; sjeme2[8][16] = 33; ro[8][16] = 25;
  344. dd2[9][2] = 19; sjeme2[9][2] = 25; ro[9][2] = 16;
  345. dd2[9][3] = 24; sjeme2[9][3] = 92; ro[9][3] = 22;
  346. dd2[9][4] = 30; sjeme2[9][4] = 70; ro[9][4] = 16;
  347. dd2[9][5] = 34; sjeme2[9][5] = 64; ro[9][5] = 27;
  348. dd2[9][6] = 39; sjeme2[9][6] = 40; ro[9][6] = 26;
  349. dd2[9][7] = 44; sjeme2[9][7] = 57; ro[9][7] = 15;
  350. dd2[9][8] = 49; sjeme2[9][8] = 88; ro[9][8] = 15;
  351. dd2[9][9] = 54; sjeme2[9][9] = 54; ro[9][9] = 16;
  352. dd2[9][10] = 59; sjeme2[9][10] = 16; ro[9][10] = 15;
  353. dd2[9][11] = 64; sjeme2[9][11] = 22; ro[9][11] = 16;
  354. dd2[9][12] = 67; sjeme2[9][12] = 93; ro[9][12] = 26;
  355. dd2[9][13] = 72; sjeme2[9][13] = 47; ro[9][13] = 16;
  356. dd2[9][14] = 77; sjeme2[9][14] = 70; ro[9][14] = 16;
  357. dd2[9][15] = 81; sjeme2[9][15] = 28; ro[9][15] = 17;
  358. dd2[9][16] = 86; sjeme2[9][16] = 28; ro[9][16] = 17;
  359. dd2[10][2] = 21; sjeme2[10][2] = 10; ro[10][2] = 15;
  360. dd2[10][3] = 26; sjeme2[10][3] = 75; ro[10][3] = 16;
  361. dd2[10][4] = 31; sjeme2[10][4] = 14; ro[10][4] = 15;
  362. dd2[10][5] = 36; sjeme2[10][5] = 52; ro[10][5] = 17;
  363. dd2[10][6] = 41; sjeme2[10][6] = 80; ro[10][6] = 25;
  364. dd2[10][7] = 46; sjeme2[10][7] = 41; ro[10][7] = 19;
  365. dd2[10][8] = 51; sjeme2[10][8] = 78; ro[10][8] = 18;
  366. dd2[10][9] = 55; sjeme2[10][9] = 97; ro[10][9] = 19;
  367. dd2[10][10] = 61; sjeme2[10][10] = 72; ro[10][10] = 15;
  368. dd2[10][11] = 65; sjeme2[10][11] = 84; ro[10][11] = 19;
  369. dd2[10][12] = 69; sjeme2[10][12] = 36; ro[10][12] = 21;
  370. dd2[10][13] = 75; sjeme2[10][13] = 90; ro[10][13] = 17;
  371. dd2[10][14] = 79; sjeme2[10][14] = 34; ro[10][14] = 23;
  372. dd2[10][15] = 84; sjeme2[10][15] = 22; ro[10][15] = 17;
  373. dd2[10][16] = 88; sjeme2[10][16] = 61; ro[10][16] = 19;
  374. dd2[11][2] = 22; sjeme2[11][2] = 51; ro[11][2] = 15;
  375. dd2[11][3] = 27; sjeme2[11][3] = 11; ro[11][3] = 17;
  376. dd2[11][4] = 33; sjeme2[11][4] = 62; ro[11][4] = 16;
  377. dd2[11][5] = 38; sjeme2[11][5] = 27; ro[11][5] = 17;
  378. dd2[11][6] = 43; sjeme2[11][6] = 85; ro[11][6] = 16;
  379. dd2[11][7] = 47; sjeme2[11][7] = 26; ro[11][7] = 16;
  380. dd2[11][8] = 53; sjeme2[11][8] = 87; ro[11][8] = 25;
  381. dd2[11][9] = 57; sjeme2[11][9] = 45; ro[11][9] = 16;
  382. dd2[11][10] = 63; sjeme2[11][10] = 78; ro[11][10] = 17;
  383. dd2[11][11] = 66; sjeme2[11][11] = 65; ro[11][11] = 20;
  384. dd2[11][12] = 72; sjeme2[11][12] = 78; ro[11][12] = 17;
  385. dd2[11][13] = 77; sjeme2[11][13] = 81; ro[11][13] = 16;
  386. dd2[11][14] = 82; sjeme2[11][14] = 78; ro[11][14] = 20;
  387. dd2[11][15] = 87; sjeme2[11][15] = 21; ro[11][15] = 16;
  388. dd2[11][16] = 90; sjeme2[11][16] = 29; ro[11][16] = 16;
  389. dd2[12][2] = 23; sjeme2[12][2] = 22; ro[12][2] = 19;
  390. dd2[12][3] = 29; sjeme2[12][3] = 101; ro[12][3] = 15;
  391. dd2[12][4] = 34; sjeme2[12][4] = 47; ro[12][4] = 17;
  392. dd2[12][5] = 39; sjeme2[12][5] = 105; ro[12][5] = 26;
  393. dd2[12][6] = 44; sjeme2[12][6] = 138; ro[12][6] = 20;
  394. dd2[12][7] = 49; sjeme2[12][7] = 96; ro[12][7] = 22;
  395. dd2[12][8] = 54; sjeme2[12][8] = 58; ro[12][8] = 16;
  396. dd2[12][9] = 60; sjeme2[12][9] = 146; ro[12][9] = 18;
  397. dd2[12][10] = 65; sjeme2[12][10] = 27; ro[12][10] = 15;
  398. dd2[12][11] = 69; sjeme2[12][11] = 105; ro[12][11] = 19;
  399. dd2[12][12] = 74; sjeme2[12][12] = 70; ro[12][12] = 19;
  400. dd2[12][13] = 79; sjeme2[12][13] = 32; ro[12][13] = 24;
  401. dd2[12][14] = 83; sjeme2[12][14] = 74; ro[12][14] = 16;
  402. dd2[12][15] = 89; sjeme2[12][15] = 27; ro[12][15] = 15;
  403. dd2[12][16] = 93; sjeme2[12][16] = 109; ro[12][16] = 19;
  404. }
  405.  
  406. void rjesi () {
  407.     int pot = 1;
  408.     while ((1 << pot) < n) pot++;
  409.     int br = prr[pot], cnt = 0;
  410.     if (dd[pot][w] < (pot + br) * w && dd[pot][w] < (2*w+1) * pot) {
  411.         if (dd[pot][w] < dd2[pot][w]) {
  412.             flg = 1;
  413.             len = dd[pot][w];
  414.             return;
  415.         } else {
  416.             flg = 2;
  417.             len = dd2[pot][w];
  418.             return;
  419.         }
  420.     } else if (dd2[pot][w] < (pot + br) * w && dd2[pot][w] < (2*w+1) * pot) {
  421.         flg = 2;
  422.         len = dd2[pot][w];
  423.         return;
  424.     }
  425.     len = (pot + br) * w;
  426.     if (len > (2*w+1) * pot) {
  427.         len = (2*w+1) * pot;
  428.         for (int i=1; i<=pot; i++) {
  429.             for (int j=1; j<=n; j++) {
  430.                 bt[i][j] = !!(j & (1 << (i-1)));
  431.             }
  432.         }
  433.         for (int i=1; i<=2*w; i++) {
  434.             for (int j=1; j<=pot; j++) {
  435.                 bt[i*pot + j] = bt[j];
  436.             }
  437.         }
  438.         return;
  439.     }
  440.     for (int i=1; i <= pot + br; i++) {
  441.         if (__builtin_popcount(i) == 1) {
  442.             bt[i] = 0;
  443.             continue;
  444.         }
  445.         for (int j=1; j<=n; j++) {
  446.             bt[i][j] = !!(j & (1 << cnt));
  447.         }
  448.         for (int j=0; j<br; j++) {
  449.             if (i & (1 << j)) {
  450.                 bt[1 << j] ^= bt[i];
  451.             }
  452.         }
  453.         cnt++;
  454.     }
  455.     for (int i=1; i<w; i++) {
  456.         for (int j=1; j <= pot + br; j++) {
  457.             bt[i*(pot + br) + j] = bt[j];
  458.         }
  459.     }
  460. }
  461.  
  462. bool check () {
  463.     for (int i=1; i<=n; i++) {
  464.         mask[i] = 0;
  465.         for (int j=1; j<=len; j++) {
  466.             mask[i][j] = bt[j][i];
  467.         }
  468.     }
  469.     for (int i=1; i<=n; i++) {
  470.         for (int j=i+1; j<=n; j++) {
  471.             if (g[i][j] == sd) continue;
  472.             if ((mask[i] ^ mask[j]).count() <= 2*w) {
  473.                 return 0;
  474.             } else {
  475.                 g[i][j] = sd;
  476.             }
  477.         }
  478.     }
  479.     return 1;
  480. }
  481.  
  482. bool pravi () {
  483.     for (int i=1; i<=n; i++) {
  484.         mask[i] = 0;
  485.         for (int j=1; j<=len; j++) {
  486.             mask[i][j] = bt[j][i];
  487.         }
  488.     }
  489.     for (int i=1; i<=n; i++) {
  490.         for (int j=i+1; j<=n; j++) {
  491.             if ((mask[i] ^ mask[j]).count() <= 2*w) return 0;
  492.         }
  493.     }
  494.     return 1;
  495. }
  496.  
  497. void dodaj(){
  498.     bt[len] = 0;
  499.     for(int k = 0;k < dens;k++){
  500.         bt[len] ^= bt[rnd_br() % (len - 1) + 1];
  501.     }
  502. }
  503.  
  504. void genv2 () {
  505.     int pot = 1;
  506.     while ((1 << pot) < n) pot++;
  507.     rnd = sd;
  508.     for (int i=1; i<=pot; i++) {
  509.         bt[i] = 0;
  510.         for (int j=1; j<=n; j++) {
  511.             bt[i][j] = !!(j & (1 << (i-1)));
  512.         }
  513.     }
  514.     len = pot;
  515.     if (pravi()) return;
  516.     for (len++; len <= m; len++) {
  517.         dodaj();
  518.         if (pravi()) break;
  519.     }
  520. }
  521.  
  522. void gen () {
  523.     for (int i=1; i<=n; i++) {
  524.         p[i] = i;
  525.     }
  526.     rnd = sd;
  527.     for (len = 1; len <= m; len++) {
  528.         rnd_shuffle();
  529.         bt[len] = 0;
  530.         for (int i=1; i<=n/2; i++) {
  531.             bt[len][p[i]] = 1;
  532.         }
  533.         if (check()) break;
  534.     }
  535. }
  536.  
  537. void genv22 () {
  538.     int pot = 1;
  539.     while ((1 << pot) < n) pot++;
  540.     rnd = sjeme2[pot][w];
  541.     for (int i=1; i<=pot; i++) {
  542.         bt[i] = 0;
  543.         for (int j=1; j<=n; j++) {
  544.             bt[i][j] = !!(j & (1 << (i-1)));
  545.         }
  546.     }
  547.     len = pot;
  548.     dens = ro[pot][w];
  549.     for (len++; len <= dd2[pot][w]; len++) {
  550.         dodaj();
  551.     }
  552.     len--;
  553. }
  554.  
  555. void gen2 (int pot) {
  556.     for (int i=1; i<=n; i++) {
  557.         p[i] = i;
  558.     }
  559.     rnd = sjeme[pot][w];
  560.     for (int clen = 1; clen <= len; clen++) {
  561.         rnd_shuffle();
  562.         bt[clen] = 0;
  563.         for (int i=1; i<=n/2; i++) {
  564.             bt[clen][p[i]] = 1;
  565.         }
  566.     }
  567. }
  568.  
  569. void ispis () {
  570.     //if (!pravi()) cout << "krivo " << n << " " << w << endl; else cout << "tocno" << endl;
  571.     cout << len << endl;
  572.     for (int i=1; i<=len; i++) {
  573.         for (int j=1; j<=n; j++) {
  574.             cout << bt[i][j];
  575.         }
  576.         cout << endl;
  577.     }
  578.     //cout << "check " << check() << endl;
  579. }
  580.  
  581. void spremi2 (int mn, int ind, int inddens) {
  582.     cout << "dd2[" << gpot << "][" << w << "] = " << mn << "; ";
  583.     cout << "sjeme2[" << gpot << "][" << w << "] = " << ind << "; ";
  584.     cout << "ro[" << gpot << "][" << w << "] = " << inddens << "; " << endl;
  585. }
  586.  
  587. void spremi (int mn, int ind) {
  588.     cout << "dd[" << gpot << "][" << w << "] = " << mn << "; ";
  589.     cout << "sjeme[" << gpot << "][" << w << "] = " << ind << "; " << endl;
  590. }
  591.  
  592.  
  593. void ispis2 () {
  594.     int pot = 1;
  595.     while ((1 << pot) < n) pot++;
  596.     int org = n;
  597.     n = (1 << pot);
  598.     len = dd[pot][w];
  599.     gen2(pot);
  600.     n = org;
  601.     //if (!pravi()) cout << "krivo " << n << " " << w << endl; else cout << "tocno" << endl;
  602.     cout << len << endl;
  603.     for (int i=1; i<=len; i++) {
  604.         for (int j=1; j<=n; j++) {
  605.             cout << bt[i][j];
  606.         }
  607.         cout << endl;
  608.     }
  609. }
  610.  
  611. void ispis22 () {
  612.     int pot = 1;
  613.     while ((1 << pot) < n) pot++;
  614.     int org = n;
  615.     n = (1 << pot);
  616.     len = dd2[pot][w];
  617.     genv22();
  618.     n = org;
  619.     //if (!pravi()) cout << "krivo " << n << " " << w << endl; else cout << "tocno" << endl;
  620.     cout << len << endl;
  621.     for (int i=1; i<=len; i++) {
  622.         for (int j=1; j<=n; j++) {
  623.             cout << bt[i][j];
  624.         }
  625.         cout << endl;
  626.     }
  627. }
  628.  
  629. int main () {
  630.     ios_base::sync_with_stdio(false);
  631.     cin.tie(0);
  632.     if (1) {
  633.         precompute();
  634.         int t;
  635.         cin >> t;
  636.         //t = 10000000;
  637.         for (int i=0; i<t; i++) {
  638.             cin >> n >> w >> m;
  639.             //n = rand() % 4095 + 2;
  640.             //w = rand() % 15 + 2;
  641.             //m = 200;
  642.             flg = 0;
  643.             rjesi();
  644.             if (flg == 0) ispis(); else if (flg == 1) ispis2(); else ispis22();
  645.         }
  646.     } else {
  647.         m = 300;
  648.         gpot = 0;
  649.         for (n = (1 << 1); n <= (1 << 12); n *= 2) {
  650.             gpot++;
  651.             for (w = 2; w <= 16; w++) {
  652.                 int mn = 1000000, ind = -1, inddens;
  653.                 for (dens = 15; dens <= 27; dens++) {
  654.                     for (sd = 1; sd <= 300; sd++) {
  655.                         genv2();
  656.                         if (len < mn) {
  657.                             mn = len;
  658.                             ind = sd;
  659.                             inddens = dens;
  660.                         }
  661.                     }
  662.                 }
  663.                 spremi2(mn, ind, inddens);
  664.             }
  665.         }
  666.         /*for (n= 2; n <= (1 << 12); n++) {
  667.             cout << n << endl;
  668.             for (w=1; w<=16; w++) {
  669.                 rjesi();
  670.                 if (!check()) {
  671.                     cout << "nije dobro " << n << " " << w << endl;
  672.                     ispis();
  673.                     return 0;
  674.                 }
  675.             }
  676.         }*/
  677.     }
  678.     return 0;
  679. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!