Guest User

Untitled

a guest
Dec 3rd, 2018
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.77 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. using namespace std;
  23.  
  24. typedef unsigned long long ll;
  25.  
  26. #ifdef ONPC
  27. mt19937 rnd(228);
  28. #else
  29. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  30. #endif
  31.  
  32. const int N = 3e5 + 7;
  33. const int MOD = 998244353;
  34.  
  35. vector <ll> a[N];
  36. vector <ll> val[N][2];
  37.  
  38. int ind[3], y[3];
  39. ll cur[N];
  40. ll pw[4 * N];
  41.  
  42. int n, k, x;
  43. int ln;
  44. int res = 0;
  45.  
  46. ll ok[1 << 3];
  47.  
  48. void rec(int i, int last = 0)
  49. {
  50. if (i == x)
  51. {
  52. int s = 0;
  53. for (int i = 0; i < x; i++) s += ind[i];
  54. int lim = (1 << x);
  55. for (int mask = 0; mask < lim; mask++)
  56. {
  57. ok[mask] = 0;
  58. for (int j = 0; j < ln; j++)
  59. {
  60. ll me = val[ind[0]][mask & 1][j];
  61. for (int it = 1; it < x; it++) me &= val[ind[it]][(mask >> it) & 1][j];
  62. ok[mask] += __builtin_popcountll(me);
  63. }
  64. }
  65. int coef = 1;
  66. if (x == 2)
  67. {
  68. if (ind[0] != ind[1])
  69. {
  70. coef *= 2;
  71. }
  72. }
  73. else if (x == 3)
  74. {
  75. if (ind[0] == ind[1] && ind[1] == ind[2])
  76. {
  77. coef *= 1;
  78. }
  79. else if (ind[0] != ind[1] && ind[1] != ind[2])
  80. {
  81. coef *= 6;
  82. }
  83. else
  84. {
  85. coef *= 3;
  86. }
  87. }
  88. int cur = 0;
  89. for (int mask = 0; mask < lim; mask += 2)
  90. {
  91. cur += ((((ok[mask] * ok[(lim - 1) ^ mask]) % MOD) * pw[s]) % MOD);
  92. if (cur >= MOD) cur -= MOD;
  93. }
  94. res += (cur * (ll) coef) % MOD;
  95. if (res >= MOD) res -= MOD;
  96. }
  97. else
  98. {
  99. for (int t = last; t < k; t++)
  100. {
  101. ind[i] = t;
  102. rec(i + 1, t);
  103. }
  104. }
  105. }
  106.  
  107. int main()
  108. {
  109. #ifdef ONPC
  110. freopen("a.in", "r", stdin);
  111. #endif
  112. ios::sync_with_stdio(0);
  113. cin.tie(0);
  114. pw[0] = 1;
  115. for (int i = 1; i < 4 * N; i++)
  116. {
  117. pw[i] = (pw[i - 1] * 2) % MOD;
  118. }
  119. cin >> n >> k >> x;
  120. ln = n / 64 + 1;
  121. int len = k / 64 + 1;
  122. for (int j = 0; j < k; j++)
  123. {
  124. for (int t = 0; t < 2; t++)
  125. {
  126. val[j][t].resize(ln);
  127. }
  128. }
  129. for (int i = 0; i < n; i++)
  130. {
  131. a[i].resize(len);
  132. string s;
  133. cin >> s;
  134. for (int j = 0; j < k; j++)
  135. {
  136. val[j][s[j] - '0'][i / 64] |= (1ll << (i % 64));
  137. if (s[j] == '1')
  138. {
  139. a[i][j / 64] |= (1ll << (j % 64));
  140. }
  141. }
  142. }
  143. if (n <= k * (ll) k / 2)
  144. {
  145. ll pw = 1;
  146. for (int it = 0; it < 64; it++)
  147. {
  148. pw = (pw * 2) % MOD;
  149. }
  150. ll sum = 0;
  151. for (int i = 0; i < n; i++)
  152. {
  153. for (int j = i + 1; j < n; j++)
  154. {
  155. ll ans = 0;
  156. for (int it = len - 1; it >= 0; it--)
  157. {
  158. ll ret = (a[i][it] ^ a[j][it]) % MOD;
  159. ans = (ans * pw + ret) % MOD;
  160. }
  161. ll ok = 1;
  162. for (int it = 0; it < x; it++) (ok *= ans) %= MOD;
  163. sum = (sum + ok) % MOD;
  164. }
  165. }
  166. cout << sum << '\n';
  167. }
  168. else
  169. {
  170. res = 0;
  171. rec(0);
  172. cout << res << '\n';
  173. }
  174. }
Add Comment
Please, Sign In to add comment