fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //#pragma GCC optimize("O3")
  4. //#pragma GCC optimize("unroll-loops")
  5. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  6. #define int long long
  7. #define fast ios::sync_with_stdio(false); cin.tie(nullptr);
  8. const int M = 998244353;
  9. const int G = 3;
  10. const int N = 2000005;
  11.  
  12. unsigned int p[N];
  13. unsigned int f[N];
  14. unsigned int v[N];
  15.  
  16. unsigned int pwr(unsigned int a, unsigned int b) {
  17.     unsigned int r = 1;
  18.     a %= M;
  19.     while (b > 0) {
  20.         if (b % 2 == 1) r = 1ULL * r * a % M;
  21.         a = 1ULL * a * a % M;
  22.         b /= 2;
  23.     }
  24.     return r;
  25. }
  26.  
  27. unsigned int inv(unsigned int a) {
  28.     return pwr(a, M - 2);
  29. }
  30.  
  31. void pre() {
  32.     f[0] = 1;
  33.     v[0] = 1;
  34.     for (int i = 1; i < N; i++) f[i] = 1ULL * f[i - 1] * i % M;
  35.     v[N - 1] = inv(f[N - 1]);
  36.     for (int i = N - 2; i >= 1; i--) v[i] = 1ULL * v[i + 1] * (i + 1) % M;
  37. }
  38.  
  39. void Ntt(vector<unsigned int>& a, bool b) {
  40.     int n = a.size();
  41.     for (int i = 1, j = 0; i < n; i++) {
  42.         int k = n >> 1;
  43.         for (; j & k; k >>= 1) j ^= k;
  44.         j ^= k;
  45.         if (i < j) swap(a[i], a[j]);
  46.     }
  47.     for (int x = 2; x <= n; x <<= 1) {
  48.         unsigned int w = pwr(G, (M - 1) / x);
  49.         if (b) w = inv(w);
  50.         for (int i = 0; i < n; i += x) {
  51.             unsigned int z = 1;
  52.             for (int j = 0; j < x / 2; j++) {
  53.                 unsigned int u = a[i + j];
  54.                 unsigned int y = 1ULL * a[i + j + x / 2] * z % M;
  55.                 a[i + j] = (u + y >= M ? u + y - M : u + y);
  56.                 a[i + j + x / 2] = (u < y ? u - y + M : u - y);
  57.                 z = 1ULL * z * w % M;
  58.             }
  59.         }
  60.     }
  61.     if (b) {
  62.         unsigned int r = inv(n);
  63.         for (unsigned int &x : a) x = 1ULL * x * r % M;
  64.     }
  65. }
  66.  
  67. vector<unsigned int> mul(vector<unsigned int> const& a, vector<unsigned int> const& b) {
  68.     if (a.empty() || b.empty()) return {};
  69.     vector<unsigned int> x(a.begin(), a.end()), y(b.begin(), b.end());
  70.     int n = 1;
  71.     while (n < a.size() + b.size()) n <<= 1;
  72.     x.resize(n); y.resize(n);
  73.     Ntt(x, false); Ntt(y, false);
  74.     for (int i = 0; i < n; i++) x[i] = 1ULL * x[i] * y[i] % M;
  75.     Ntt(x, true);
  76.     vector<unsigned int> r(a.size() + b.size() - 1);
  77.     for (int i = 0; i < r.size(); i++) r[i] = x[i];
  78.     return r;
  79. }
  80.  
  81. signed main(){
  82.     fast
  83.  
  84.     if (fopen("mint.inp", "r")){
  85.         freopen("mint.inp", "r", stdin);
  86.         freopen("mint.out", "w", stdout);
  87.     }
  88.     pre();
  89.     int n, q; cin >> n >> q;
  90.     int d = n;
  91.     for (int i = 0; i <= n; i++) cin >> p[i];
  92.  
  93.  
  94.     unsigned int c = 0;
  95.     unsigned int l = 0;
  96.  
  97.     for (int i = 0; i < q; i++) {
  98.         char o; cin >> o;
  99.  
  100.         if (o == 'D') {
  101.             if (d >= 0) {
  102.                 if (c == 0) {
  103.                     for (int j = 0; j < d; j++) p[j] = p[j + 1];
  104.                     p[d] = 0;
  105.                     d--;
  106.                 } 
  107.                 else {
  108.                     unsigned int x = p[d];
  109.                     p[d] = 0;
  110.                     for (int j = d - 1; j >= 0; j--) {
  111.                         unsigned int y = p[j];
  112.                         p[j] = x;
  113.                         x = (y + 1ULL * c * x) % M;
  114.                     }
  115.                     d--;
  116.                 }
  117.             }
  118.         } 
  119.         else if (o == 'S') {
  120.             unsigned int x;
  121.             cin >> x;
  122.             x ^= l;
  123.             c = (c + x) % M;
  124.         } 
  125.         else if (o == 'M') {
  126.             int m; cin >> m;
  127.             vector<unsigned int> b(m);
  128.             for (int j = 0; j < m; j++) cin >> b[j];
  129.  
  130.             if (c != 0) {
  131.                 vector<unsigned int> x(m);
  132.                 for (int j = 0; j < m; j++) x[j] = 1ULL * b[j] * f[j] % M;
  133.                 vector<unsigned int> y(m);
  134.                 for (int j = 0; j < m; j++) y[j] = x[m - 1 - j];
  135.  
  136.                 vector<unsigned int> z(m);
  137.                 unsigned int u = (M - c) % M;
  138.                 unsigned int w = 1;
  139.                 for (int j = 0; j < m; j++) {
  140.                     z[j] = 1ULL * w * v[j] % M;
  141.                     w = 1ULL * w * u % M;
  142.                 }
  143.  
  144.                 vector<unsigned int> k = mul(y, z);
  145.  
  146.                 vector<unsigned int> r(m);
  147.                 for (int j = 0; j < m; j++) r[j] = 1ULL * k[m - 1 - j] * v[j] % M;
  148.                 b = r;
  149.             }
  150.  
  151.             if (d >= 0) {
  152.                 vector<unsigned int> x(p, p + d + 1);
  153.                 vector<unsigned int> y = mul(x, b);
  154.                 d = y.size() - 1;
  155.                 for (int j = 0; j <= d; j++) p[j] = y[j];
  156.             }
  157.         } 
  158.         else if (o == 'Q') {
  159.             int t; cin >> t;
  160.             t ^= l;
  161.  
  162.             unsigned int a = 0;
  163.             if (t > d) a = 0;
  164.             else {
  165.                 if (c == 0) a = 1ULL * p[t] * f[t] % M;
  166.                 else {
  167.                     unsigned int x = 0;
  168.                     for (int j = d; j >= t; j--) {
  169.                         unsigned int y = 1ULL * p[j] * f[j] % M * v[j - t] % M;
  170.                         x = (1ULL * x * c + y) % M;
  171.                     }
  172.                     a = x;
  173.                 }
  174.             }
  175.             cout << a << "\n";
  176.             l = a;
  177.         }
  178.     }
  179.     return 0;
  180. }
  181.  
Success #stdin #stdout 0.12s 36124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dzuYBk
language:
C++14 (clang 8.0)
created:
10 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!