YZOJ P4611 区间加多项式（YJC 的数组/多项式？）

时间限制：4444MS      内存限制：1048576KB

难度：\(7.2\)

• 题目描述

由于本题之前被*了，所以现在数据就是随便造的，可能会因为太水又被艹     //给出题人留点面子吧qwq

YJC 在 AK 了一场校内之后，对其中的一题（P2036 「A Simple Data Structure Problem II 」）产生了兴趣。

于是他出了一题加强版（P4316 「ASDSP VII —— YJC树」），然而，他还是觉得这个加强版太简单啦！！！

所以，这次，他不仅把 \(K \leq 5\) 往后面加了三个零变成了 \(K \leq 5000\) ，还对询问做了一点修改！

喜欢差分的 YJC 有一个长度为 \(N\) 的数组 \(c\)，初始值都为 \(0\)，下标编号为 \(1, 2, \cdots, N\) 。

现在 YJC 忙着 AK CSP-S2019，没空验证数据的正确性，所以只能把这个重任交给了你 —— ******，希望你能写一个程序帮他实现以下的几个操作：

\(opt=1\)，给定 \(L, R\)，输出 \(\sum\limits_{i=L}^R c_i\) 的值对 \(998244353\) 取模后的结果；

\(opt=0\)，给定 \(L, R\) 以及 \(K\) 次多项式 \(f(x)=\sum\limits_{k=0}^K a_kx^k\)，对 \(c_L, c_{L+1}, \cdots, c_R\) 分别加上 \(f(1), f(2), \cdots, f(R-L+1)\) 的值。

• 输入格式

第一行两个正整数 \(N, Q\) ，分别表示区间范围 \([1, N]\) 及询问数 \(Q\) 。

接下来，每行（除了每个 \(opt=0\) 操作的下一行）的第一个数 \(opt\) 表示操作类型。

若 \(opt=0\)，则接下来有两个正整数 \(L, R\) 表示操作的区间 \([L, R]\)。紧接着下一行的第一个整数 \(K\) 表示多项式的最高次数为 \(K\) ，接下来 \(K+1\) 个整数 \(a_0, a_1, \cdots, a_K\) 分别表示多项式 \(f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k\) 的系数；

若 \(opt=1\)，则接下来有两个正整数 \(L, R\) 表示询问的区间 \([L, R]\)。

因为 YJC 忙着 AK CSP-S2019（之前说过了），所以他一不小心把数据给加密了。

记 \(lastans\) 为上一个 \(opt=1\) 询问输出的答案（没有则为 \(0\)）：对于读入的 \(L\) 和 \(R\)，\(L \;\mbox{xor} \left(lastans^2\right)\) 及 \(R \;\mbox{xor} \left(lastans^2\right)\) 分别为真实的 \(L\) 和 \(R\)；对于读入的 \(a_k \left(0 \leq k \leq K\right)\)，\(a_k \;\mbox{xor}\; lastans\) 为真实的 \(a_k\)。\(\mbox{xor}\) 表示二进制下的异或操作。

（友情提示：数据范围保证的是真实的输入数据的范围。）

• 输出格式

对于每个 \(opt=1\) 操作，输出一行一个数表示答案。

• 样例输入

• 样例输出

• 样例说明

初始 \(c_9\) 为 \(0\) ，输出 \(0\)；

对 \([8, 9]\) 加上 \(f(x)=1\) ；

现在 \(c_9\) 为 \(1\) ，输出 \(1\)；

\(lastans=1\)，真实的 \(L=3 \;\mbox{xor} \left(1^2\right)=2\)，\(R=8 \;\mbox{xor} \left(1^2\right)=9\)，\(a_0=a_1=a_2=0 \;\mbox{xor}\; 1=1\) ，即对 \([2, 9]\) 加上 \(f(x)=1+x+x^2\) ；

\(lastans=1\)，真实的 \(L=8 \;\mbox{xor} \left(1^2\right)=9\)，\(R=11 \;\mbox{xor} \left(1^2\right)=10\)，即询问 \(c_9+c_{10}\)，输出 \(\left(1+1+8+8^2\right)+0=74\)。

• 数据规模与约定

本题采用子任务制，即只有通过了该子任务下的所有测试点，才能得到其相应的分数。

对于所有的测试点，有 \(1 \leq N \leq 10^{18}\)，\(0 \leq Q \leq 100000\)，\(0 \leq K \leq 5000\)；

\(1 \leq L \leq R \leq N\)，\(\forall i \in [0, K]: 0 \leq \left|a_i\right| < 998244353\)。

设每个 \(opt=0\) 操作的 \(K\) 分别为 \(k_1, k_2, \cdots, k_s\) ，记 \(tk = \displaystyle\sum\limits_{i=1}^s {\left(k_i+1\right)}\)。

同时记 \(opt=1\) 操作的总次数为 \(tq\) 。

Subtask 1 （\(1pts\)）

\(N \leq 10^5\)，\(K \leq 0\)，\(Q \leq 100000\)，\(tk, tq \leq 50500\)。

Subtask 2 （\(2pts\)）

\(K \leq 0\)，\(Q \leq 100000\)，\(tk, tq \leq 50500\)。

Subtask 3 （\(3pts\)）

\(N \leq 10^5\)，\(K \leq 1\)，\(Q \leq 100000\)，\(tk \leq 75500\)，\(tq \leq 50500\)。

Subtask 4 （\(4pts\)）

\(K \leq 1\)，\(Q \leq 100000\)，\(tk \leq 65000\)，\(tq \leq 50550\)。

Subtask 5 （\(5pts\)）

\(N \leq 10^5\)，\(K \leq 2\)，\(Q \leq 100000\)，\(tk \leq 84000\)，\(tq \leq 50500\)。

Subtask 6 （\(6pts\)）

\(K \leq 2\)，\(Q \leq 100000\)，\(tk \leq 100000\)，\(tq \leq 10500\)。

Subtask 7 （\(7pts\)）

\(N \leq 10^5\)，\(K \leq 5\)，\(Q \leq 100000\)，\(tk \leq 175785\)，\(tq \leq 49884\)。

Subtask 8 （\(8pts\)）

\(K \leq 5\)，\(Q \leq 80000\)，\(tk \leq 110000\)，\(tq \leq 80000\)。

Subtask 9 （\(24pts\)）

\(K \leq 500\)，\(Q \leq 1000\)，\(tk \leq 220000\)，\(tq \leq 250\)。

Subtask 10 （\(35pts\)）

\(K \leq 5000\)，\(Q \leq 75\)，\(tk \leq 150000\)，\(tq \leq 50\)。

Subtask 11 （\(5pts\)）

\(K = 5000\)，\(Q \leq 50\)。

如果是根据数据范围选择做法的w也卡不了了qaq

 

 

 

---

 

 

 

区间加多项式 及 区间查询。

本来只有单点查询的，结果被 L****n * 过去了，然后就变成了难受的区间查询）

本来所有的 \(Q\) 都是 \(\leq 50\) 的，结果被 *agoo* * 过去了，然后就变成了难受的 \(Q\) 和 \(K\) 成反比）

如果 \(N, K\) 比较小的话可以考虑离线差分，开多个树状数组维护。但是本题中 \(N, K\) 都较大，并且强制在线，需要另寻出路。

 

考虑若修改的区间均为 \([1, R]\)，那么实际上只需要维护这些多项式对应次数的系数和即可。因为 \(c_i\) 与 \(f(i)\) 对应，所以对于相同的 \(i^k\) 其系数可以合并。

所以可以把 \(c_i\) 看成一个多项式 \(g(x)\) 在 \(x=i\) 处的值，且 \(g(x)\) 的各项系数为这些多项式的对应次数的系数和。

即若要加入一个多项式 \(f(x)\)，因为 \(c_i\) 需要加上 \(f(i)\)，而 \(c_i = g(i)\)，所以直接把 \(g(x)\) 的各项系数加上 \(f(x)\) 的对应次数的系数即可；

若要查询某一个 \(c_i\) 的值，只需要求出 \(g(x)\) 的每项系数然后把 \(x=i\) 带入即可。

由于 \(K \leq 5000\)，所以可以开 \(K\) 棵动态开点线段树分别维护每个 \(g(x)\) 的对应项系数，支持区间修改和单点查询即可。

然而现在要修改的区间为 \([L, R]\)，即 \(c_i\) 与 \(f\left(i-L+1\right)\) 对应，\(i^k\) 与 \(\left(i-L+1\right)^k\) 不同所以系数无法直接合并。

所以这里有一个简单粗暴办法，可以平移 \(f(x)\) 强行使得 \(c_i\) 与 \(f(i)\) 对应，然后就可以直接合并了。

原本 \(c_i\) 与 \(f\left(i-L+1\right)\) 对应，要使 \(c_i\) 与 \(f(i)\) 对应，所以把 \(f(x)\) 平移成 \(f(x-L+1)\)，这样带入 \(x=i\) 是得到的就是 \(f(i-L+1)\) 的值了。

即若 \(f(x) = \displaystyle\sum\limits_{k=0}^K a_kx^k\)，那么平移后的 \(h(x) = f(x+c) = \displaystyle\sum\limits_{k=0}^K a_k\left(x+c\right)^k\)，其中 \(c=-L+1\) 。

根据二项式定理展开，有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}} \sum\limits_{j = 0}^k {\left( {\begin{array}{*{20}{c}} {k}\\ j \end{array}} \right) {x^j}{c^{k – j}}}\) 。

交换求和次序，有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {{x^j}\sum\limits_{k = j}^K {{a_k} \left( {\begin{array}{*{20}{c}} {k}\\ j \end{array}} \right) } } {c^{k – j}}\) 。

这样 \(h(x)\) 就可以在 \(O(K^2)\) 的时间复杂度内求出来了。

继续处理，设 \(t=k-j\)，则 \(k=t+j\)，有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {{x^j}\sum\limits_{t = 0}^{K – j} {{a_{j+t}} \left( {\begin{array}{*{20}{c}} {j + t}\\ j \end{array}} \right)} } {c^t}\) 。

组合数拆开，有 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}}\sum\limits_{t = 0}^{K – j} {{a_{j + t}}\left( {j + t} \right)!} } \frac{{{c^t}}}{{t!}}\) 。

其实已经可以看出来这是一个卷积的形式了。

再做处理，设 \(A_k = a_{K-k}\left(K-k\right)!\)，\(B_k = \displaystyle\frac{c^k}{k!}\)，则 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}}\sum\limits_{t = 0}^{K – j} {{A_{K – j – t}}} {B_t}}\) 。

设 \(g(n) = \displaystyle\sum\limits_{t = 0}^n {{A_{n – t}}} {B_t}\)，可以用 NTT（任意模数FFT） 在 \(O(K \log K)\) 的复杂度内求出 \(n=0, 1, \cdots, K\) 时函数的取值。

最后 \(h(x) = \displaystyle\sum\limits_{j = 0}^K {\frac{{{x^j}}}{{j!}} g(K-j)}\) 就可以得到 \(h(x)\) 的各项系数了。

 

但是上面的方法仅适用于单点查询，区间查询怎么办？

发现每次询问一个点必须要 \(O(\max\{K\} \log n)\) 的复杂度，由于把 \(c_i\) 看成是多项式的单点值这个设定，所以很难在数据结构等方面有其他的突破。

所以可以考虑在多项式等方面做些处理。

只支持单点查询，又要求区间和，所以可以想到维护 \(c\) 的前缀和。

这样加入一个多项式 \(f(x)\)，就相当于在 \([L, R]\) 区间加它的前缀多项式 \(h(x)\)，在 \((R, N]\) 区间加常数 \(h(R)\) 。

区间查询时只需查询 \(c_R\) 和 \(c_{L-1}\) 两单点值即可。

前缀多项式 \(h(x) = \displaystyle\sum\limits_{j=1}^x f(j)\)，即 \(h(x) = \displaystyle\sum\limits_{j=1}^x \sum\limits_{k=0}^K a_kj^k\)。

展开，有 \(h(x) = \cdots\cdots\cdots\) 。

等等，这怎么展开？？？里面好像有类似于 \(j^k\) （自然数幂和）的东西，这怎么搞？

这里选用伯努利公式：\(\displaystyle\sum\limits_{k=1}^x k^n = 1^n+2^n+\cdots+x^n = \frac{1}{{n + 1}}\mathop \sum \limits_{k = 0}^n \left( {\begin{array}{*{20}{c}} {n + 1}\\ k \end{array}} \right)B_k^ + {x^{n + 1 – k}}\) 。

其中 \(B_k^+\) 为伯努利数的第 \(k\) 项，\(\displaystyle B_0=1,B_1^\pm=\pm\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=\frac{1}{30},\cdots\) 。

伯努利数的定义式为 \({B_0} = 1\)，\(\displaystyle\sum\limits_{i = 0}^n {B_i} \left( {\begin{array}{*{20}{c}} {n + 1}\\ i \end{array}} \right) = 0\) 。

所以可以得到其递推式为 \(B_0 = 1\)，\(B_n =  -\displaystyle\frac{1}{{n + 1}}\sum\limits_{i = 0}^{n – 1} {\left( {\begin{array}{*{20}{c}} {n + 1}\\ i \end{array}} \right){B_i}} \) ，可以在 \(O(K^2)\) 的时间复杂度内算出来，或打表 \(O(1)\)，或多项式求逆 \(O(K \log K)\)。

然后就可以继续推 \(h(x)\) 了。

交换求和顺序，有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}} \sum\limits_{j = 1}^x {{j^k}} \) 。

应用上面的公式，有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}\frac{1}{{k + 1}}\sum\limits_{j = 0}^k {\left( {\begin{array}{*{20}{c}} {k + 1}\\ j \end{array}} \right)} B_j^ + {x^{k + 1 – j}}} \) 。

换元，设 \(t=k-j\)，则 \(j=k-t\)，有 \(h(x) = \displaystyle\sum\limits_{k = 0}^K {{a_k}\frac{1}{{k + 1}}\sum\limits_{t = 0}^k {\left( {\begin{array}{*{20}{c}} {k + 1}\\ {k – t} \end{array}} \right)} B_{k – t}^ + {x^{t + 1}}} \) 。

再次交换求和顺序，有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {{x^{t + 1}}\sum\limits_{k = t}^K {\frac{{{a_k}}}{{k + 1}}\left( {\begin{array}{*{20}{c}} {k + 1}\\ {k – t} \end{array}} \right)} B_{k – t}^ + } \) 。

这样 \(h(x)\) 就可以在 \(O(K^2)\) 的时间复杂度内求出来了。

组合数展开，再整理，有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}}\sum\limits_{k = t}^K {{a_k}k!\frac{{B_{k – t}^ + }}{{\left( {k – t} \right)!}}} } \) 。

是不是很熟悉？再换元，设 \(j=k-t\)，则有 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}}\sum\limits_{j = 0}^{K – t} {{a_{j + t}}\left( {j + t} \right)!\frac{{B_j^ + }}{{j!}}} } \) 。

是不是更熟悉了？设 \(A_k = a_{K-k}\left(K-k\right)!\)，\(C_k = \displaystyle\frac{{B_j^ + }}{{j!}}\)，则 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}} \sum\limits_{j = 0}^{K – t} A_{K-t-j}C_j }\) 。

设 \(g(n) = \displaystyle\sum\limits_{j = 0}^n {{A_{n – j}}} {C_j}\)，可以用 NTT（任意模数FFT） 在 \(O(K \log K)\) 的复杂度内求出 \(n=0, 1, \cdots, K\) 时函数的取值。

最后 \(h(x) = \displaystyle\sum\limits_{t = 0}^K {\frac{{{x^{t + 1}}}}{{(t + 1)!}} g(K-t)}\) 就可以得到 \(h(x)\) 的各项系数了。

 

一个类似于总结的东西

区间加多项式（基本区间操作）：线段树；（标记永久化比打 \(tag\) 时间和空间都小了一半以上）

多项式平移（支持任意区间修改）：FFT；

多项式前缀和（支持区间查询）：FFT。

 

所以本题本来应该是 FFT+FFT+线 段树，时间复杂度 \(O(QK \log N + QK \log K)\)，常数巨大。

由于后面 \(Q\) 很小，所以直接暴力是能跑过的，然后你就可以 * 标算了）