https://www.luogu.com.cn/problem/U329489
给出一个长度为 n 的数列
接下来进行 m 次操作
1 l r k a
i = l ~ r A[i] += k * a ^ (i - l)
2 l r k a
i = l ~ r sum A[i] * k * a ^ (i - l)
最后输出一遍整个序列
输出对998244353取模
n,m <= 1e5, 5s
操作分块+序列分块
首先假设每B次操作整个重构一遍 块内修改对询问贡献的复杂度即为 mB
考虑如何重构。
首先散块暴力，设分块块长为B2，这部分复杂度即为 mB2
整块
考虑修改
不难发现整块序列所得的贡献形式的生成函数是一个有理分式，可以用分治ntt+多项式求逆解决
let b = max(B,B2), b log ^ 2 b
考虑查询
不难发现一个块对多个询问的影响可以写成多点求值的形式 b log ^ 2 b
散块部分暴力即可 mB2
总复杂度即为 m(B+B2)+m/B * n/B2 * b log ^ 2 b
设n,m同阶 取 B = B2 = sqrt n log n
n sqrt n log n
有一点卡常。