SHARE
TWEET

Untitled

a guest Dec 3rd, 2018 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
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
 
Top