結果
| 問題 | No.2265 Xor Range Substring Sum Query |
| ユーザー |
 jiangly
|
| 提出日時 | 2023-04-07 22:06:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,066 ms / 5,000 ms |
| コード長 | 7,405 bytes |
| コンパイル時間 | 1,861 ms |
| コンパイル使用メモリ | 200,824 KB |
| 最終ジャッジ日時 | 2025-02-12 01:28:43 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using i64 = long long;template<class T>constexpr T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;}constexpr i64 mul(i64 a, i64 b, i64 p) {i64 res = a * b - i64(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;}template<i64 P>struct MLong {i64 x;constexpr MLong() : x{} {}constexpr MLong(i64 x) : x{norm(x % getMod())} {}static i64 Mod;constexpr static i64 getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(i64 Mod_) {Mod = Mod_;}constexpr i64 norm(i64 x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr i64 val() const {return x;}explicit constexpr operator i64() const {return x;}constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs;return res;}friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs;return res;}friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs;return res;}friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {i64 v;is >> v;a = MLong(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}};template<>i64 MLong<0LL>::Mod = 1;template<int P>struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(i64 x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {i64 v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}};template<>int MInt<0>::Mod = 1;template<int V, int P>constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 998244353;using Z = MInt<P>;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;int N = 1 << n;int n1 = n / 2;int n2 = n - n1;std::string s;std::cin >> s;std::vector<int> S(N);for (int i = 0; i < N; i++) {S[i] = s[i] - '0';}std::vector<Z> f(N);const Z p = Z(2) / 11;auto build = [&](int hi) {int x = hi << n2;for (int i = 0; i < (1 << n2); i++) {f[x + i] = S[x + i];}for (int i = 1; i < (1 << n2); i *= 2) {Z pw = power(p, i);for (int j = 0; j < (1 << n2); j += 2 * i) {for (int k = 0; k < i; k++) {Z a = f[x + j + k];Z b = f[x + i + j + k];f[x + j + k] = a + b * pw;f[x + i + j + k] = b + a * pw;}}}};for (int i = 0; i < (1 << n1); i++) {build(i);}std::vector<Z> P(N);P[0] = 1;for (int i = 1; i < N; i++) {P[i] = P[i - 1] * p;}int Q;std::cin >> Q;while (Q--) {int t;std::cin >> t;if (t == 1) {int x, y;std::cin >> x >> y;for (int i = 0; i < (1 << n2); i++) {f[x ^ i] += P[i] * (y - S[x]);}S[x] = y;} else {int L, R, X;std::cin >> L >> R >> X;Z pw = power(p, 1 << n2);Z v = 1;Z ans = 0;for (int i = 0; i < (1 << n1); i++) {int l = std::max(i << n2, L);int r = std::min((i + 1) << n2, R + 1);if (r - l == (1 << n2)) {ans += f[l ^ X] * v;v *= pw;} else if (l < r) {for (int j = l; j < r; j++) {ans += S[j ^ X] * v;v *= p;}}}ans *= power(Z(11), R - L);std::cout << ans << "\n";}}return 0;}