Zbq's Music Challenge
题意：
一个长度为n的序列，每个位置可能是1或者0，1的概率是$p_i$。对于一个序列$S$，它的得分是
$$BasicScore=A\times \sum_{i=1}^{n}{S_i} \tag{1}$$
$$ combo(i)=\left\{ \begin{aligned} &S_i & &i=1 \\ &combo(i-1)+1 & &i\neq 1 ~\mathrm{and}~ S_i=1 \\ &combo(i-1)\times t & &\mathrm{otherwise} \end{aligned} \tag{2} \right.$$
$$ComboScore=B\times \sum_{i=1}^{n}{S_i\times combo(i)} \tag{3}$$
$$TotalScore=BasicScore+ComboScore \tag{4}$$
两种操作，修改每个位置的概率，询问一段区间得分的期望，答案对$998244353$取模。
分析：
分成两部分算，$BasicScore$可以对$p_i$求和得到。
对于每段区间，$f[i]$设第i位置数字期望是多少，那么$ComboScore = B \times \sum\limits_{i=l}^{r} p_i \times (f[i-1] + 1) $。
然后转移可以写成矩阵的形式。
$$ \left[ \begin{matrix} 1 & p_i & p_i \\ 0 & (1 - p_i) \times t + p_i & p_i\\ 0 & 0 & 1 \end{matrix} \right] \times \left[ \begin{matrix} sum\\ f[i - 1]\\ 1 \end{matrix} \right] = \left[ \begin{matrix} sum' \\ f[i]\\ 1 \end{matrix} \right] $$
于是，线段树维护一下即可。复杂度$O(nlogn \times 3^3)$
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int mod = ;
const int N = ;
int p[N]; int ksm(int a,int b) {
int res = ;
while (b) {
if (b & ) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return res;
}
int fen(int a,int b) { return 1ll * a * ksm(b, mod - ) % mod; } int sum[N << ], tt, NowAns, n, A, B;
struct Mat{
int a[][];
Mat() { memset(a, , sizeof(a)); }
void set(int p) {
a[][] = ;
a[][] = a[][] = a[][] = p;
a[][] = (1ll * (mod + - p) % mod * tt % mod + p) % mod;
a[][] = ;
}
}T[N << ];
Mat operator * (const Mat &A, const Mat &B) {
Mat C;
for (int k = ; k < ; ++k)
for (int i = ; i < ; ++i)
for (int j = ; j < ; ++j)
C.a[i][j] = (C.a[i][j] + 1ll * A.a[i][k] * B.a[k][j] % mod) % mod;
return C;
}
inline void pushup(int rt) {
T[rt] = T[rt << ] * T[rt << | ];
sum[rt] = (sum[rt << ] + sum[rt << | ]) % mod;
}
void build(int l,int r,int rt) {
if (l == r) {
T[rt].set(p[l]); sum[rt] = p[l]; return ;
}
int mid = (l + r) >> ;
build(l, mid, rt << ); build(mid + , r, rt << | );
pushup(rt);
}
void update(int l,int r,int rt,int pos) {
if (l == r) {
T[rt].set(p[l]); sum[rt] = p[l]; return ;
}
int mid = (l + r) >> ;
if (pos <= mid) update(l, mid, rt << , pos);
else update(mid + , r, rt << | , pos);
pushup(rt);
}
Mat query(int l,int r,int rt,int L,int R) {
if (L <= l && r <= R) { NowAns = (NowAns + sum[rt]) % mod; return T[rt]; }
int mid = (l + r) >> ;
if (R <= mid) return query(l, mid, rt << , L, R);
else if (L > mid) return query(mid + , r, rt << | , L, R);
else return query(l, mid, rt << , L, R) * query(mid + , r, rt << | , L, R);
}
void query() {
int x = read(), y = read();
NowAns = ;
Mat now = query(, n, , x, y);
LL ans1 = NowAns, ans2 = now.a[][];
cout << (1ll * ans1 * A % mod + 1ll * ans2 * B % mod) % mod << "\n";
}
int main() {
read();
n = read();int Q = read(), ta = read(), tb = read();A = read(), B = read();
tt = fen(ta, tb);
for (int i = ; i <= n; ++i)
ta = read(), tb = read(), p[i] = fen(ta, tb);
build(, n, );
while (Q --) {
if (read()) query();
else {
int x = read(), ta = read(), tb = read();
p[x] = fen(ta, tb);
update(, n, , x);
}
}
return ;
}