結果

問題 No.2498 OX Operations
コンテスト
ユーザー SSRS
提出日時 2023-10-06 22:06:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,108 ms / 4,000 ms
コード長 2,417 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 212,208 KB
最終ジャッジ日時 2025-02-17 05:07:05
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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 + MOD;
  }
  ans %= MOD;
  cout << ans << endl;
}
0