結果
問題 |
No.1189 Sum is XOR
|
ユーザー |
![]() |
提出日時 | 2020-08-02 00:54:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 1,525 bytes |
コンパイル時間 | 1,064 ms |
コンパイル使用メモリ | 90,292 KB |
最終ジャッジ日時 | 2025-01-12 13:02:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <iostream> #include <unordered_map> #include <vector> using namespace std; using lint = int64_t; constexpr lint mod = 998244353; inline bool f(int x, int y) { return x + y == (x xor y); } lint inv(lint x) { lint res = 1, expo = mod - 2; while (expo > 0) { if (expo & 1) { res *= x; res %= mod; } x *= x; x %= mod; expo >>= 1; } return res; } lint solve(int n, int k, const vector<int>& a) { lint res = 0; if (11 <= k) return 0; else { unordered_map<int, lint>cnt; for (int i = 0; i < n; i++) { cnt[a[i]]++; } if (k == 2) { for (auto [i, cnt1] : cnt) { for (auto [j, cnt2] : cnt) { if (f(i, j)) res += cnt1 * cnt2; } } return res / 2 % mod; } else { vector<unordered_map<int, lint>>mp_vec(k - 2); for (auto [i, cnt1] : cnt) { for (auto [j, cnt2] : cnt) { if (f(i, j)) mp_vec[0][i xor j] += cnt1 * cnt2; } } for (int i = 0; i < k - 2; i++) { for (auto [key, value] : mp_vec[i]) { for (auto [j, cnt1] : cnt) { if (f(key, j)) { if (i < k - 3) { mp_vec[i + 1][key xor j] += cnt1 * value % mod; mp_vec[i + 1][key xor j] %= mod; } else { res += cnt1 * value % mod; res %= mod; } } } } } lint fact = 1; for (lint i = 2; i <= k; i++) { fact *= i; fact %= mod; } return res * inv(fact) % mod; } } } int main() { int n, k; cin >> n >> k; vector<int>a(n); for (int& e : a) cin >> e; cout << solve(n, k, a) << endl; }