fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 998244353;
  5. const int N = 200005;
  6.  
  7. int modpow(int a, int e, int mod) {
  8.     int res = 1;
  9.     while (e) {
  10.         if (e & 1) res = 1LL * res * a % mod;
  11.         a = 1LL * a * a % mod;
  12.         e >>= 1;
  13.     }
  14.     return res;
  15. }
  16.  
  17. int inv(int x) {
  18.     return modpow(x, MOD - 2, MOD);
  19. }
  20.  
  21. struct Matrix {
  22.     int m[3][3];
  23.     Matrix() {
  24.         for (int i = 0; i < 3; i++)
  25.             for (int j = 0; j < 3; j++)
  26.                 m[i][j] = (i == j ? 1 : 0);
  27.     }
  28.     Matrix operator*(const Matrix& other) const {
  29.         Matrix res;
  30.         for (int i = 0; i < 3; i++) {
  31.             for (int j = 0; j < 3; j++) {
  32.                 long long sum = 0;
  33.                 for (int k = 0; k < 3; k++) {
  34.                     sum += 1LL * m[i][k] * other.m[k][j] % MOD;
  35.                 }
  36.                 res.m[i][j] = sum % MOD;
  37.             }
  38.         }
  39.         return res;
  40.     }
  41. };
  42.  
  43. Matrix gold(int a, int b, int c) {
  44.     Matrix M;
  45.     long long S = (1LL * a * a + 1LL * b * b) % MOD;
  46.     long long invS = inv(S);
  47.     // M = I - [a; b; 0] * [a, b, c] * invS
  48.     M.m[0][0] = (1 - 1LL * a * a % MOD * invS % MOD + MOD) % MOD;
  49.     M.m[0][1] = (0 - 1LL * a * b % MOD * invS % MOD + MOD) % MOD;
  50.     M.m[0][2] = (0 - 1LL * a * c % MOD * invS % MOD + MOD) % MOD;
  51.     M.m[1][0] = (0 - 1LL * a * b % MOD * invS % MOD + MOD) % MOD;
  52.     M.m[1][1] = (1 - 1LL * b * b % MOD * invS % MOD + MOD) % MOD;
  53.     M.m[1][2] = (0 - 1LL * b * c % MOD * invS % MOD + MOD) % MOD;
  54.     M.m[2][0] = 0;
  55.     M.m[2][1] = 0;
  56.     M.m[2][2] = 1;
  57.     return M;
  58. }
  59.  
  60. Matrix diamond(int a, int b, int c) {
  61.     Matrix M;
  62.     long long S = (1LL * a * a + 1LL * b * b) % MOD;
  63.     long long invS = inv(S);
  64.     M.m[0][0] = (1 - 2LL * a * a % MOD * invS % MOD + MOD) % MOD;
  65.     M.m[0][1] = (0 - 2LL * a * b % MOD * invS % MOD + MOD) % MOD;
  66.     M.m[0][2] = (0 - 2LL * a * c % MOD * invS % MOD + MOD) % MOD;
  67.     M.m[1][0] = (0 - 2LL * a * b % MOD * invS % MOD + MOD) % MOD;
  68.     M.m[1][1] = (1 - 2LL * b * b % MOD * invS % MOD + MOD) % MOD;
  69.     M.m[1][2] = (0 - 2LL * b * c % MOD * invS % MOD + MOD) % MOD;
  70.     M.m[2][0] = 0;
  71.     M.m[2][1] = 0;
  72.     M.m[2][2] = 1;
  73.     return M;
  74. }
  75.  
  76. Matrix seg[4 * N];
  77. Matrix mats[N];
  78.  
  79. void build(int idx, int l, int r) {
  80.     if (l == r) {
  81.         seg[idx] = mats[l];
  82.         return;
  83.     }
  84.     int mid = (l + r) / 2;
  85.     build(idx * 2, l, mid);
  86.     build(idx * 2 + 1, mid + 1, r);
  87.     seg[idx] = seg[idx * 2 + 1] * seg[idx * 2]; // thứ tự ngược: r...l
  88. }
  89.  
  90. void update(int idx, int l, int r, int pos, Matrix val) {
  91.     if (l == r) {
  92.         seg[idx] = val;
  93.         return;
  94.     }
  95.     int mid = (l + r) / 2;
  96.     if (pos <= mid) update(idx * 2, l, mid, pos, val);
  97.     else update(idx * 2 + 1, mid + 1, r, pos, val);
  98.     seg[idx] = seg[idx * 2 + 1] * seg[idx * 2];
  99. }
  100.  
  101. Matrix query(int idx, int l, int r, int ql, int qr) {
  102.     if (ql <= l && r <= qr) return seg[idx];
  103.     int mid = (l + r) / 2;
  104.     if (qr <= mid) return query(idx * 2, l, mid, ql, qr);
  105.     if (ql > mid) return query(idx * 2 + 1, mid + 1, r, ql, qr);
  106.     return query(idx * 2 + 1, mid + 1, r, ql, qr) * query(idx * 2, l, mid, ql, qr);
  107. }
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(false);
  111.     cin.tie(nullptr);
  112.  
  113.     int n, q;
  114.     cin >> n >> q;
  115.  
  116.     for (int i = 1; i <= n; i++) {
  117.         char ch;
  118.         int a, b, c;
  119.         cin >> ch >> a >> b >> c;
  120.         a = (a % MOD + MOD) % MOD;
  121.         b = (b % MOD + MOD) % MOD;
  122.         c = (c % MOD + MOD) % MOD;
  123.         if (ch == 'G') {
  124.             mats[i] = gold(a, b, c);
  125.         } else {
  126.             mats[i] = diamond(a, b, c);
  127.         }
  128.     }
  129.  
  130.     build(1, 1, n);
  131.  
  132.     while (q--) {
  133.         int t;
  134.         cin >> t;
  135.         if (t == 1) {
  136.             int j, a, b, c;
  137.             char m;
  138.             cin >> j >> m >> a >> b >> c;
  139.             a = (a % MOD + MOD) % MOD;
  140.             b = (b % MOD + MOD) % MOD;
  141.             c = (c % MOD + MOD) % MOD;
  142.             if (m == 'G') {
  143.                 update(1, 1, n, j, gold(a, b, c));
  144.             } else {
  145.                 update(1, 1, n, j, diamond(a, b, c));
  146.             }
  147.         } else {
  148.             int x, y, l, r;
  149.             cin >> x >> y >> l >> r;
  150.             x = (x % MOD + MOD) % MOD;
  151.             y = (y % MOD + MOD) % MOD;
  152.             Matrix M = query(1, 1, n, l, r);
  153.             int xf = (1LL * M.m[0][0] * x + 1LL * M.m[0][1] * y + M.m[0][2]) % MOD;
  154.             int yf = (1LL * M.m[1][0] * x + 1LL * M.m[1][1] * y + M.m[1][2]) % MOD;
  155.             cout << xf << " " << yf << "\n";
  156.         }
  157.     }
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0.02s 38748KB
comments (?)
stdin
copy 
2 5
G 1 0 -1
D 0 1 -1
2 3 5 1 1
2 3 5 1 2
1 2 D 1 1 0
2 3 5 1 2
2 6 9 2 2
stdout
copy 
1 5
1 998244350
998244348 998244352
998244344 998244347
https://ideone.com/xwgtMP
language:
C++ (gcc 8.3)
created:
16 days 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!