結果
問題 | No.1493 隣接xor |
ユーザー |
|
提出日時 | 2021-12-04 23:54:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 942 bytes |
コンパイル時間 | 1,522 ms |
コンパイル使用メモリ | 179,036 KB |
実行使用メモリ | 20,480 KB |
最終ジャッジ日時 | 2024-07-07 06:50:45 |
合計ジャッジ時間 | 6,666 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using namespace atcoder;using ll = long long;#define rep(i, n) for (int i = 0; i < (n); i++)#define ALL(x) (x).begin(), (x).end()#define SZ(x) (int)(x).size()using mint = modint998244353;int main() {ll N;cin >> N;vector<ll> A(N);rep(i, N) cin >> A[i];vector<ll> cum(N + 1, 0);rep(i, N) cum[i + 1] = cum[i] ^ A[i];vector<mint> dp(N + 1, 0);dp[0] = 1;map<ll, int> Rid;vector<mint> dpcum(N + 2, 0); // dp[0,i)の和dpcum[1] = 1;for (int i = 1; i <= N; i++) {int j = Rid[cum[i]];// for (int k = j; k < i; k++) dp[i] += dp[k];dp[i] = dpcum[i] - dpcum[j];dpcum[i + 1] = dpcum[i] + dp[i];Rid[cum[i]] = i;}mint ans = 0;for (int i = 1; i <= N; i++) {if (cum[N] == cum[i]) ans += dp[i];}cout << ans.val() << '\n';return 0;}