結果

問題 No.2498 OX Operations
ユーザー SSRSSSRS
提出日時 2023-10-06 22:05:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,411 bytes
コンパイル時間 2,554 ms
コンパイル使用メモリ 215,876 KB
実行使用メモリ 28,496 KB
最終ジャッジ日時 2023-10-06 22:05:48
合計ジャッジ時間 15,624 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 7 ms
4,380 KB
testcase_13 AC 5 ms
4,376 KB
testcase_14 AC 8 ms
4,376 KB
testcase_15 AC 836 ms
21,260 KB
testcase_16 WA -
testcase_17 AC 759 ms
18,428 KB
testcase_18 AC 1,043 ms
25,464 KB
testcase_19 AC 957 ms
23,060 KB
testcase_20 AC 1,050 ms
27,096 KB
testcase_21 AC 1,104 ms
27,940 KB
testcase_22 AC 444 ms
14,112 KB
testcase_23 AC 350 ms
12,864 KB
testcase_24 AC 1,126 ms
28,472 KB
testcase_25 AC 1,124 ms
28,496 KB
testcase_26 AC 1,148 ms
28,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0