fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops,inline")
  2. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef unsigned int ui;
  9. typedef unsigned long long ull;
  10.  
  11. #define rep(i, a, b) for (int i = (a); i < (b); ++i)
  12. #define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
  13. #define z(x) ((int)(x).size())
  14.  
  15. #define ADD(u, v) { u += v; if (u >= P) u -= P; }
  16. #define SUB(u, v) { u -= v; if (u < 0) u += P; }
  17.  
  18. const int P = 998244353, G = 3, MX = 1 << 20;
  19. int fc[MX], ifc[MX], rt[MX], irt[MX], iv2[MX];
  20. alignas(64) static int na[MX * 2], nb[MX * 2];
  21.  
  22. ll pw(ll a, ll b) {
  23.     ll r = 1;
  24.     a %= P;
  25.     for (; b; b >>= 1, a = a * a % P) {
  26.         if (b & 1) r = r * a % P;
  27.     }
  28.     return r;
  29. }
  30.  
  31. void pre() {
  32.     fc[0] = 1;
  33.     rep(i, 1, MX) fc[i] = (ll)fc[i - 1] * i % P;
  34.  
  35.     ifc[MX - 1] = pw(fc[MX - 1], P - 2);
  36.     per(i, 0, MX - 1) ifc[i] = (ll)ifc[i + 1] * (i + 1) % P;
  37.  
  38.     rt[1] = irt[1] = 1;
  39.     for (int k = 2; k < MX; k <<= 1) {
  40.         int w = pw(G, (P - 1) / (2 * k)), iw = pw(w, P - 2);
  41.         rt[k] = irt[k] = 1;
  42.         rep(i, 1, k) {
  43.             rt[k + i] = (ll)rt[k + i - 1] * w % P;
  44.             irt[k + i] = (ll)irt[k + i - 1] * iw % P;
  45.         }
  46.     }
  47.  
  48.     iv2[0] = 1;
  49.     int h = (P + 1) / 2;
  50.     rep(i, 1, MX) iv2[i] = (ll)iv2[i - 1] * h % P;
  51. }
  52.  
  53. void ntt(int* a, int n, int f) {
  54.     for (int i = 1, j = 0; i < n; i++) {
  55.         int b = n >> 1;
  56.         for (; j & b; b >>= 1) j ^= b;
  57.         j ^= b;
  58.         if (i < j) swap(a[i], a[j]);
  59.     }
  60.  
  61.     int* rv = (f == 1) ? rt : irt;
  62.     for (int len = 1; len < n; len <<= 1) {
  63.         for (int i = 0; i < n; i += 2 * len) {
  64.             rep(j, 0, len) {
  65.                 int u = a[i + j], v = (ll)a[i + j + len] * rv[len + j] % P;
  66.                 a[i + j] = u; 
  67.                 ADD(a[i + j], v);
  68.                 a[i + j + len] = u; 
  69.                 SUB(a[i + j + len], v);
  70.             }
  71.         }
  72.     }
  73. }
  74.  
  75. void ts(int* a, int n, int c) {
  76.     rep(k, 0, n) na[n - 1 - k] = (ll)a[k] * fc[k] % P;
  77.  
  78.     int s = 1;
  79.     while (s < 2 * n - 1) s <<= 1;
  80.     rep(k, n, s) na[k] = 0;
  81.  
  82.     int ck = 1;
  83.     rep(k, 0, n) {
  84.         nb[k] = (ll)ck * ifc[k] % P;
  85.         ck = (ll)ck * c % P;
  86.     }
  87.     rep(k, n, s) nb[k] = 0;
  88.  
  89.     ntt(na, s, 1);
  90.     ntt(nb, s, 1);
  91.     rep(k, 0, s) na[k] = (ll)na[k] * nb[k] % P;
  92.     ntt(na, s, -1);
  93.  
  94.     int g = __builtin_ctz(s), w = iv2[g];
  95.     rep(k, 0, n) a[k] = (ll)na[n - 1 - k] * w % P * ifc[k] % P;
  96. }
  97.  
  98. vector<int> ml(vector<int> a, vector<int> b) {
  99.     int n = z(a) + z(b) - 1, s = 1;
  100.     while (s < n) s <<= 1;
  101.  
  102.     rep(k, 0, z(a)) na[k] = a[k];
  103.     rep(k, z(a), s) na[k] = 0;
  104.     rep(k, 0, z(b)) nb[k] = b[k];
  105.     rep(k, z(b), s) nb[k] = 0;
  106.  
  107.     ntt(na, s, 1);
  108.     ntt(nb, s, 1);
  109.     rep(k, 0, s) na[k] = (ll)na[k] * nb[k] % P;
  110.     ntt(na, s, -1);
  111.  
  112.     int g = __builtin_ctz(s), w = iv2[g];
  113.     vector<int> r(n);
  114.     rep(k, 0, n) r[k] = (ll)na[k] * w % P;
  115.  
  116.     return r;
  117. }
  118.  
  119. int main() {
  120.     ios_base::sync_with_stdio(0);
  121.     cin.tie(0);
  122.  
  123.     pre();
  124.     int n, q;
  125.     cin >> n >> q;
  126.  
  127.     vector<int> a(n + 1);
  128.     rep(i, 0, n + 1) cin >> a[i];
  129.  
  130.     int l = 0, s = 0, o = 0;
  131.  
  132.     auto fl = [&]() {
  133.         if (s) {
  134.             if (o) {
  135.                 a.erase(a.begin(), a.begin() + min(o, z(a)));
  136.                 o = 0;
  137.             }
  138.             if (a.empty()) {
  139.                 a.push_back(0);
  140.                 return;
  141.             }
  142.             int m = z(a);
  143.             ts(a.data(), m, s);
  144.             s = 0;
  145.         }
  146.     };
  147.  
  148.     rep(ii, 0, q) {
  149.         char op;
  150.         cin >> op;
  151.  
  152.         if (op == 'D') {
  153.             if (s) {
  154.                 fl();
  155.                 if (!a.empty()) a.erase(a.begin());
  156.                 if (a.empty()) a.push_back(0);
  157.             } else {
  158.                 o++;
  159.                 if (o >= z(a)) {
  160.                     a.assign(1, 0);
  161.                     o = 0;
  162.                 }
  163.             }
  164.         } else if (op == 'S') {
  165.             ll c;
  166.             cin >> c;
  167.             c ^= l;
  168.             if (o) {
  169.                 a.erase(a.begin(), a.begin() + min(o, z(a)));
  170.                 if (a.empty()) a.push_back(0);
  171.                 o = 0;
  172.             }
  173.             s = (int)((s + c % P) % P);
  174.         } else if (op == 'M') {
  175.             fl();
  176.             if (o) {
  177.                 a.erase(a.begin(), a.begin() + min(o, z(a)));
  178.                 o = 0;
  179.             }
  180.             if (a.empty()) a.push_back(0);
  181.  
  182.             int m;
  183.             cin >> m;
  184.             vector<int> b(m);
  185.             rep(i, 0, m) cin >> b[i];
  186.  
  187.             a = ml(a, b);
  188.             if (z(a) >= MX) a.resize(MX);
  189.         } else {
  190.             ll t;
  191.             cin >> t;
  192.             t ^= l;
  193.  
  194.             int k = (int)t + o, v = z(a);
  195.             ll e = 0;
  196.  
  197.             if (k < v) {
  198.                 if (!s) {
  199.                     e = (ll)fc[(int)t % MX] * a[k] % P;
  200.                 } else {
  201.                     ll j = 1;
  202.                     for (int i = 0; i + k < v; i++) {
  203.                         e = (e + (ll)a[i + k] * fc[i + k] % P * ifc[i] % P * j) % P;
  204.                         j = (ll)j * s % P;
  205.                     }
  206.                     e = e % P * (ll)fc[(int)t % MX] % P * ifc[k % MX] % P;
  207.                 }
  208.             }
  209.             l = (int)e;
  210.             cout << e << '\n';
  211.         }
  212.     }
  213.     return 0;
  214. }
  215.  
Success #stdin #stdout 0.02s 27328KB
comments (?)
stdin
copy 
3 6
0 0 1 0
M 3 1 0 1
Q 0
S 1
Q 0
D
Q 0
stdout
copy 
0
2
8
https://ideone.com/eweGu4
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!