結果
問題 | No.1958 Bit Game |
ユーザー |
![]() |
提出日時 | 2022-05-28 02:54:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 794 ms / 2,000 ms |
コード長 | 971 bytes |
コンパイル時間 | 3,103 ms |
コンパイル使用メモリ | 143,704 KB |
実行使用メモリ | 27,296 KB |
最終ジャッジ日時 | 2024-09-20 20:11:24 |
合計ジャッジ時間 | 21,390 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
//ビットごとにできるので、はい。 #include <iostream> #include <atcoder/all> #include <vector> #define rep(i, n) for(i = 0; i < n; i++) using namespace std; using namespace atcoder; using mint = modint998244353; typedef vector<mint> Vec; typedef vector<Vec> Mat; int n, X, Y; int a[1 << 18], b[1 << 18]; int main() { int i, j; cin >> n >> X >> Y; rep(i, X) cin >> a[i]; rep(i, Y) cin >> b[i]; mint ans = 0; rep(i, 18) { int oneA = 0, oneB = 0; rep(j, X) if ((a[j] >> i) % 2) oneA++; rep(j, Y) if ((b[j] >> i) % 2) oneB++; Mat dp(2 * n + 1, Vec(2, 0)); dp[0][0] = 1; rep(j, 2 * n) { if (j % 2 == 0) { dp[j + 1][0] += (X - oneA) * dp[j][0]; dp[j + 1][1] += oneA * dp[j][0]; dp[j + 1][1] += X * dp[j][1]; } else { dp[j + 1][0] += Y * dp[j][0]; dp[j + 1][0] += (Y - oneB) * dp[j][1]; dp[j + 1][1] += oneB * dp[j][1]; } } ans += (1 << i) * dp[2 * n][1]; } cout << ans.val() << endl; return 0; }