「校内训练2019-09-22」迫真随机序列

Description

有一个$n$个数的序列,我们现在可以在其中任意添加加号和乘号,我们总共可以得到$2^{n-1}个表达式,运算符的优先级是正常的,让你求所有序列的和。
答案对998244353取模

Data Range

$2\leq n,q\leq 200000,1\leq p+i\leq n,0\leq a_i,v_i<998244353$

Solution

考虑一个二元组的$DP$,状态$(a,b)$表示当前和加入的这一个数毫不相关的前一段和尾$a$,前面的$\times $后连接的是$b$,那么插入一个$c$之后,我们就讨论一下。如果是$+$号,转移后得到$(a+b,c)$,如果是$\times $号,转移后得到$(a,b\times c)$。
我们考虑用矩阵来转移,发现不能转移,我们就扩大一元$(a,b,1)$。
可以得到$+$的矩阵是

1 0 0
1 0 0
0 c 1

得到$\times $的矩阵是

1 0 0
0 c 0
0 0 1

矩阵满足分配率,所以可以把两个矩阵合并成一个,然后依次转移就可以了。

Code

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T& x) {
  x = 0; bool flg = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) flg |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  flg ? x = -x : 233;
}
const int MOD = 998244353;
int pw(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = 1ll * x * x % MOD)
    if (y & 1) res = 1ll * res * x % MOD;
  return res;
}
int inv(int x) { return pw(x, MOD - 2); }
void pls(int& x, int y) { (x += y) >= MOD ? x -= MOD : 233; }
int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
int mul(int x, int y) { return 1ll * x * y % MOD; }
int dec(int x, int y) { return (x -= y) < 0 ? x += MOD : x; }
struct _matrix {
  int mat[5][5];
  _matrix() { memset(mat, 0, sizeof mat); }
  void set_val(int x) {
    mat[1][1] = 2, mat[1][2] = 0, mat[1][3] = 0;
    mat[2][1] = 1, mat[2][2] = x, mat[2][3] = 0;
    mat[3][1] = 0, mat[3][2] = x, mat[3][3] = 2;
  }
  _matrix operator * (const _matrix& b) const {
    _matrix res;
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++)
        for (int k = 1; k <= 3; k++)
          pls(res.mat[i][j], mul(mat[i][k], b.mat[k][j]));
    return res;
  }
} t;
const int N = 2e5 + 3;
int n, q;
int a[N];
struct _seg {
  #define lc (nod << 1)
  #define rc (nod << 1 | 1)
  _matrix tr[N << 2];
  void build(int nod, int l, int r) {
    if (l == r) { tr[nod].set_val(a[l]); return; }
    int mid = (l + r) >> 1;
    build(lc, l, mid); build(rc, mid + 1, r);
    tr[nod] = tr[lc] * tr[rc];
  }
  void modify(int nod, int l, int r, int pos, int val) {
    if (l == r) { tr[nod].set_val(val); return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(lc, l, mid, pos, val);
    else modify(rc, mid + 1, r, pos, val);
    tr[nod] = tr[lc] * tr[rc];
  }
} sgt;
void solve() {
  _matrix ans = t * sgt.tr[1];
  int res = (ans.mat[1][1] + ans.mat[1][2]) % MOD;
  res = dec(res, pw(2, n - 1));
  res = mul(res, inv(2));
  printf("%d\n", res);
}
int main() {
  read(n); read(q);
  for (int i = 1; i <= n; i++) read(a[i]);
  sgt.build(1, 1, n);
  t.mat[1][2] = t.mat[1][3] = 1;
  solve();
  while (q--) {
    int pos, val;
    read(pos); read(val);
    a[pos] = val;
    sgt.modify(1, 1, n, pos, val);
    solve();
  }
  return 0;
}
最后修改:2019 年 09 月 22 日 04 : 10 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论