Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <set>
- #include <map>
- #include <list>
- #include <time.h>
- #include <math.h>
- #include <random>
- #include <deque>
- #include <queue>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- #include <iomanip>
- #include <bitset>
- #include <sstream>
- #include <chrono>
- using namespace std;
- typedef unsigned long long ll;
- #ifdef ONPC
- mt19937 rnd(228);
- #else
- mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
- #endif
- const int N = 3e5 + 7;
- const int MOD = 998244353;
- vector <ll> a[N];
- vector <ll> val[N][2];
- int ind[3], y[3];
- ll cur[N];
- ll pw[4 * N];
- int n, k, x;
- int ln;
- int res = 0;
- ll ok[1 << 3];
- void rec(int i, int last = 0)
- {
- if (i == x)
- {
- int s = 0;
- for (int i = 0; i < x; i++) s += ind[i];
- int lim = (1 << x);
- for (int mask = 0; mask < lim; mask++)
- {
- ok[mask] = 0;
- for (int j = 0; j < ln; j++)
- {
- ll me = val[ind[0]][mask & 1][j];
- for (int it = 1; it < x; it++) me &= val[ind[it]][(mask >> it) & 1][j];
- ok[mask] += __builtin_popcountll(me);
- }
- }
- int coef = 1;
- if (x == 2)
- {
- if (ind[0] != ind[1])
- {
- coef *= 2;
- }
- }
- else if (x == 3)
- {
- if (ind[0] == ind[1] && ind[1] == ind[2])
- {
- coef *= 1;
- }
- else if (ind[0] != ind[1] && ind[1] != ind[2])
- {
- coef *= 6;
- }
- else
- {
- coef *= 3;
- }
- }
- int cur = 0;
- for (int mask = 0; mask < lim; mask += 2)
- {
- cur += ((((ok[mask] * ok[(lim - 1) ^ mask]) % MOD) * pw[s]) % MOD);
- if (cur >= MOD) cur -= MOD;
- }
- res += (cur * (ll) coef) % MOD;
- if (res >= MOD) res -= MOD;
- }
- else
- {
- for (int t = last; t < k; t++)
- {
- ind[i] = t;
- rec(i + 1, t);
- }
- }
- }
- int main()
- {
- #ifdef ONPC
- freopen("a.in", "r", stdin);
- #endif
- ios::sync_with_stdio(0);
- cin.tie(0);
- pw[0] = 1;
- for (int i = 1; i < 4 * N; i++)
- {
- pw[i] = (pw[i - 1] * 2) % MOD;
- }
- cin >> n >> k >> x;
- ln = n / 64 + 1;
- int len = k / 64 + 1;
- for (int j = 0; j < k; j++)
- {
- for (int t = 0; t < 2; t++)
- {
- val[j][t].resize(ln);
- }
- }
- for (int i = 0; i < n; i++)
- {
- a[i].resize(len);
- string s;
- cin >> s;
- for (int j = 0; j < k; j++)
- {
- val[j][s[j] - '0'][i / 64] |= (1ll << (i % 64));
- if (s[j] == '1')
- {
- a[i][j / 64] |= (1ll << (j % 64));
- }
- }
- }
- if (n <= k * (ll) k / 2)
- {
- ll pw = 1;
- for (int it = 0; it < 64; it++)
- {
- pw = (pw * 2) % MOD;
- }
- ll sum = 0;
- for (int i = 0; i < n; i++)
- {
- for (int j = i + 1; j < n; j++)
- {
- ll ans = 0;
- for (int it = len - 1; it >= 0; it--)
- {
- ll ret = (a[i][it] ^ a[j][it]) % MOD;
- ans = (ans * pw + ret) % MOD;
- }
- ll ok = 1;
- for (int it = 0; it < x; it++) (ok *= ans) %= MOD;
- sum = (sum + ok) % MOD;
- }
- }
- cout << sum << '\n';
- }
- else
- {
- res = 0;
- rec(0);
- cout << res << '\n';
- }
- }
Add Comment
Please, Sign In to add comment