题目描述
有一个长度为\(n(n\le 10^5)\)的数列，在模\(M\)意义下进行\(m(m \le50000)\)次操作，每次操作形如以下两种形式：
1 \(x\) 表示每个数加\(x(0 \le x<M)\)；
2 表示每个数对模数\(M\)取逆元，保证逆元存在。
输出每次操作后所有数的和，对\(M\)取模。这里\(M=998244353\)。
简要题解
设原始数列为\(x_i\)。对于一个初始的数\(x\)，经过第i个操作后一定可以写成\(\dfrac {a_i \times x+b_i} {c_i \times x+d_i}\)的形式。先用线性时间求出参量\(a_i,b_i,c_i,d_i\)，于是问题转化为对每个\(i\)，求出\(\displaystyle \sum\limits_{j = 1}^n {\frac{{{a_i}{x_j} + {b_i}}}{{{c_i}x_j + {d_i}}}} \)。先将整数提取出来，只需考虑\(\displaystyle \sum\limits_{j = 1}^n {\frac{{e_i}}{{{c_i}x_j + {d_i}}}} \)。
（1）若\(c_i=0\)，则直接计算即可；
（2）否则，对每个\(i\)可以归一化为求\(\displaystyle \sum\limits_{j = 1}^n {\frac{{{1}}}{{{x_j} + {t_i}}}} \)。
将分母通分，则转化为\(\dfrac {P(t_i)} {Q(t_i)}\)，其中\(P,Q\)为\(t_i\)的不超过\(n\)次多项式。
这里\(Q(x)=(x+x_1) \cdots (x+x_n)\)。考虑如何快速求出\(P\)。不难发现\(P\)正是\(Q\)的导数。
于是问题转化成了多点求值问题。可在\(O(n(\log n)^2+m(\log m)^2)\)时间复杂度求解。
还应注意到不会出现\(P(t_i)=Q(t_i)=0\)的情况，因为根据洛必达法则，此时极限趋于无穷大，不会是有限值，而题目保证了逆元存在。
说明
最近看了大量多项式应用的问题，绝大多数都是多项式逆元，这是见到的第一道应用多项式的多点求值的问题（非裸题），搞明白后不禁感叹：好题啊！佩服出题人系列。
核心代码
int x[], y[], w[], k[];
int ans1[], ans2[];
int main()
{
int n, m, op, t, sum = ;
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++){
scanf("%d", &x[i]);
sum = add(sum, x[i]);
x[i] = -x[i];
}
vector<Poly> v();
mulInit(, n, x, v);
Poly q = v[], p = diff(q);
int a = , b = , c = , d = , cnt = ;
for (int i = ; i < m; i++){
scanf("%d", &op);
if (op == ){
scanf("%d", &t);
a = add(a, mul(t, c));
b = add(b, mul(t, d));
}
else{ swap(a, c); swap(b, d); }
if (c){
int t = power(c, MOD - );
w[i] = mul(mul(a, t), n);
k[i] = mul(sub(b, mul(a, mul(d, t))), t);
y[cnt++] = mul(d, t);
}
else{
int t = power(d, MOD - );
w[i] = mul(add(mul(a, sum), mul(b, n)), t);
k[i] = -;
}
}
mulInit(, cnt, y, v);
getVal(, cnt, p, v, ans1);
getVal(, cnt, q, v, ans2);
for (int i = , j = ; i < m; i++){
if (k[i] == -)printf("%d\n", w[i]);
else{
int t = mul(ans1[j], power(ans2[j], MOD - ));
printf("%d\n", add(w[i], mul(k[i], t)));
j++;
}
}
}