前两个题应该放娱乐区。
1
题面
区间加，区间求在模 \(998244353\) 意义下的乘积，要求做到 \(O(n\sqrt n\log^2n)\)。
做法
考虑操作分块加多项式多点求值，每个块内的多项式为 \(\prod_{i=1}^k(x+x_i)\)。可以做到 \(O(n\sqrt n\log^2n)\)。
常数太大了，没写（不如暴力）。
2
题面
区间加，区间求倒数之和在模 \(998244353\) 意义下的值（保证区间内任何数均不为 \(998244353\) 的倍数），要求做到 \(O(n\sqrt n\log^2n)\)。
做法
依旧是考虑操作分块加多项式多点求值，每个块内的多项式为 \(\prod_{i=1}^k(x+x_i)\) 和 \(\sum_{i=1}^k(\prod_{j=1}^{i-1}(x+x_j)\prod_{j=i+1}^{n}(x+x_j))\)，然后就可以做到 \(O(n\sqrt n\log^2n)\)。
依旧是大常，比前面更没个写头（不如暴力）。
3
题面
自己造的题。
区间求 \((\sum_{i=l}^ra_ia_{l+r-i})\bmod998244353\) 的值，要求做到 \(O(n\sqrt{n\log n})\)。
做法
唯一一个常数还能算的上能卡掉暴力的题（当然你需要贺一个较快的多项式板子）。
注意到对于总共有 \((2n-1)\) 个不同的 \(l+r\)，每个 \(l+r\) 与处理出来 \([1,r+l],[1+\sqrt{n\log n},l+r-\sqrt{n\log n}]...\) 就可以做到 \(O(\sqrt{n\log n})\) 查询。总共 \(O(n\sqrt{\frac{n}{\log n}})\) 个区间。每次 NTT 可以耗费 \(O(n\log n)\) 的代价知道 \(O(n)\) 个区间的值，总共需要 \(O(\sqrt{\frac{n}{\log n}})\) 次 NTT，总复杂度是 \(O(n\sqrt{n\log n})\)。
卡了 \(+\infty\) 年的常也是大概能跑过暴力，实在卡常卡不过去可以找我要代码。