結果
問題 | No.2498 OX Operations |
ユーザー | SSRS |
提出日時 | 2023-10-06 22:05:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,411 bytes |
コンパイル時間 | 2,756 ms |
コンパイル使用メモリ | 218,440 KB |
実行使用メモリ | 28,580 KB |
最終ジャッジ日時 | 2024-07-26 16:10:21 |
合計ジャッジ時間 | 14,742 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 3 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 5 ms
6,940 KB |
testcase_14 | AC | 8 ms
6,944 KB |
testcase_15 | AC | 828 ms
21,452 KB |
testcase_16 | WA | - |
testcase_17 | AC | 757 ms
18,688 KB |
testcase_18 | AC | 1,040 ms
25,612 KB |
testcase_19 | AC | 1,002 ms
23,424 KB |
testcase_20 | AC | 1,062 ms
27,208 KB |
testcase_21 | AC | 1,085 ms
28,352 KB |
testcase_22 | AC | 427 ms
14,420 KB |
testcase_23 | AC | 356 ms
12,892 KB |
testcase_24 | AC | 1,113 ms
28,576 KB |
testcase_25 | AC | 1,106 ms
28,580 KB |
testcase_26 | AC | 1,115 ms
28,444 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> using namespace std; const int LOG = 30; const int ALL = (1 << LOG) - 1; const long long MOD = 998244353; struct S{ array<int, 2> A; S(){ A[0] = 0; A[1] = ALL; } S(int x, int y){ A[0] = x; A[1] = y; } }; S op(S L, S R){ S ans; ans.A[0] = (ALL ^ L.A[0]) & R.A[0] | L.A[0] & R.A[1]; ans.A[1] = (ALL ^ L.A[1]) & R.A[0] | L.A[1] & R.A[1]; return ans; } S e(){ return S(); } int main(){ int N, Q; cin >> N >> Q; vector<int> M(N); for (int i = 0; i < N; i++){ cin >> M[i]; M[i]++; } vector<char> C(Q); vector<int> L(Q), R(Q), X(Q); for (int i = 0; i < Q; i++){ cin >> C[i] >> L[i] >> R[i] >> X[i]; L[i]--; } vector<vector<int>> add(N + 1), sub(N + 1); for (int i = 0; i < Q; i++){ add[L[i]].push_back(i); sub[R[i]].push_back(i); } atcoder::segtree<S, op, e> ST(Q); vector<S> res(N); for (int i = 0; i < N; i++){ for (int j : add[i]){ if (C[j] == 'o'){ ST.set(j, S(X[j], ALL)); } if (C[j] == 'x'){ ST.set(j, S(X[j], ALL ^ X[j])); } } for (int j : sub[i]){ ST.set(j, S()); } res[i] = ST.all_prod(); } vector<vector<int>> B(LOG + 1, vector<int>(N, 0)); for (int i = 0; i < N; i++){ vector<vector<vector<int>>> dp(LOG + 1, vector<vector<int>>(2, vector<int>(LOG + 1, 0))); dp[LOG][0][0] = 1; for (int j = LOG - 1; j >= 0; j--){ for (int k = 0; k < 2; k++){ for (int l = 0; l <= LOG - 1 - j; l++){ for (int m = 0; m < 2; m++){ if (!((M[i] >> j & 1) == 0 && k == 0 && m == 1)){ int k2 = k; if ((M[i] >> j & 1) == 1 && m == 0){ k2 = 1; } int m2 = res[i].A[m] >> j & 1; dp[j][k2][l + m2] += dp[j + 1][k][l]; } } } } } for (int j = 0; j <= LOG; j++){ B[j][i] = dp[0][1][j] % MOD; } } for (int i = 0; i < N; i++){ for (int j = 0; j < LOG; j++){ B[j + 1][i] += B[j][i]; B[j + 1][i] %= MOD; } } long long t = 1; for (int i = 0; i < N; i++){ t *= M[i]; t %= MOD; } long long ans = 0; for (int i = 0; i <= LOG; i++){ long long prod = 1; for (int j = 0; j < N; j++){ prod *= B[i][j]; prod %= MOD; } ans += t - prod; } ans %= MOD; cout << ans << endl; }