暑假（2）
NOIP2023模拟测试赛（八）
A
\(k\) 条路径共同经过的路径形成一条链。路径的其他部分要么停在链端点，要么发散开来，不重叠。
假设链为 \(u,v\)。我们考虑计算以 \(u\) 为链一端的方案数。
1.若 \(u,v\) 不为祖孙关系
枚举 \(u\) 一端发散开来的路径数量 \(i\)：
\[S_u=\sum_{i=0}^kA_{k}^i[x^i]\prod_{z\in son_u}(1+siz_zx) \]这是链以 \(u\) 为一端的方案数。后面的多项式可以 \(\mathcal O(d\log^2d)\) 分治 NTT，\(d\) 为度数。
总的方案数就是 \((\sum S_u)^2\)，但是要减去：
-
\(u,v\) 为祖孙关系的情况。
-
\(u,v\) 重合的情况。
第一种情况即 \(2\sum_{u}S_u\sum_{v\in subtree_u,v\not=u}S_v\)。第二种情况即 \(\sum S_u^2\)。
最后还要除以一个 \(2\)，原题说路径是无序的。
2.若 \(u,v\) 为祖孙关系
假设 \(u\) 为祖先。枚举 \(v\) 方向上的 \(u\) 的儿子 \(w\)，以及 \(u\) 发散出的路径数量 \(i\)，总方案数为：
\[\sum_{u}\sum_{w\in son_u}\left(\sum_{v\in subtree_w}S_v\right)\sum_{i=0}^kA_k^i[x^i]\left[(1+(n-siz_u)x)\prod_{z\in son_u,z\not=w}(1+siz_zx)\right] \]\[\sum_{u}\sum_{i=0}^kA_k^i[x^i]\left[(1+(n-siz_u)x)\sum_{w\in son_u}\left(\sum_{v\in subtree_w}S_v\right)\prod_{z\in son_u,z\not=w}(1+siz_zx)\right] \]后面中括号括起来的部分同样可以 \(\mathcal O(d\log^2d)\) 分治 NTT。
再维护一下子树的 \(S_v\) 之和，即可 \(\mathcal O(n\log^2n)\) 解决此题。
B
\(A,B\) 从高到低位，所有相同的都可以删去，找到第一个不相同的位置 \(k\)。
设 \(K=2^k\)。假设 \(A,B\) 前面相同的位已经删去，现在将区间 \([A,B]\) 内数划分成两部分：\([A,K)\) 与 \([K,B]\)。
例如，假设删完最高相同位的 \(A,B\) 与 \(K\) 如下：
-
\(\text A=(00110001)_2\)
-
\(\text K=(10000000)_2\)
-
\(\text B=(10011010)_2\)
首先，\([A,B]\) 内的数一定可以被取到。
考虑 \([A,K)\) 内部的数组合：这些数 \(\texttt{OR}\) 出来一定在 \([A,B]\) 内，我们不考虑了。
\([A,K)\) 与 \([K,B]\) 内的组合：可以发现有且仅有 \([K+A,2K)\) 内的数可以被取到。
证明，这些数可以被取到是显然的。为什么只有这些数？
上界也是显然的，至于下界，由于越 \(\texttt{OR}\) 越大，我们只考虑两个数的情况。
如果存在 \(X\in[A,K),Y\in[K,B]\) 满足 \(X or Y<K+A\)，由于 \(A+K\le X+K=XorK\le Xor Y\)，
会出现 \(A+K<A+K\)，矛盾。因此得证。
然后考虑 \([K,B]\) 内部的数组合。容易发现，我们找到 \(B\) 第二高位的 \(1\)，则这之后的位置都可以是 \(0,1\)。
例如 \(\text B=(10011010)_2\)，则 \([(10010000)_2,(10011111)_2]\) 都可以取到。
把这三个区间并起来即为答案。复杂度 \(\mathcal O(\log V)\)。
C
手玩一下，如果是四个数 \(a,b,c,d\)，操作一下 \(a\) 变成 \(a\oplus b\oplus c\oplus d,b,c,d\)。
再操作一下 \(b\)，变成 \(a\oplus b\oplus c\oplus d,a,c,d\)。再操作一下 \(a\) 就变成了 \(b,a,c,d\)。
这个交换操作让我们想到另一个典型问题，将一个排列 \(p\) 交换两项，最小次数得到另一个排列 \(q\)。
那个问题的解决方案是，将 \(p_i\) 向 \(q_i\) 连边，会形成若干环。每个环需要 \(len-1\) 次操作。
这题类似地，首先有解当且仅当两个数列中数最多有一个不同，且 \(b\) 中不同的数恰好是 \(a\) 的异或和 \(s=\oplus_{i=1}^n a_i\)。
把 \(a_i\) 向 \(b_i\) 连边，由于有重复的数，不一定会形成若干个环。
我们想完成的是，对每条边把每个 \(u\) 变成 \(v\)。考虑对于一个连通块，如果其中有一个数等于 \(s\)，从它出发沿边的反向顺序操作可以 \(siz\) 次操作搞定连通块内所有数。
如果没有 \(s\)，随便操作一个数让它变成 \(s\) 即可。
dfs 看一下这个连通块内是否有 \(s\)，有的话操作次数为 \(siz\)，否则为 \(siz+1\)。
复杂度线性。
NOIP2023模拟测试赛（九）
A
要求最小 \(n\) 满足存在 \(\binom nm=x\)。只统计 \(2m\le n\) 的情况。
发现 \(\binom{2m}m\) 增长速度很快。\(\binom{64}{32}\) 已经大于 \(10^{18}\)，因此只统计 \(m\le31\) 的情况。
\(m=1,2\) 是平凡的。剩下的枚举 \(m\)，二分求是否有 \(n\) 满足条件。
实现上有小细节，可能有些地方会爆 long long 乃至 __int128。
B
傻卵题，把 \((u,v)\) 看作状态，其中 \(u\) 在第一个图上，\(v\) 在第二个图上，建立一个新图。
然后求哪些状态能到达终止节点，只考虑这些状态再找一下是否有环即可。
C
D
一个欧拉序合法当且仅当：对于每个 \([l,r]\) 满足 \(a_l=a_r\)，
-
\(r-l+1\) 是奇数。
-
\([l,r]\) 内的 \(a\) 共有 \(\frac{r-l+2}2\) 种不同的权值。
这是因为从 \(u\) 走出去再走回来，欧拉序列长度应为经过的边数的两倍加 \(1\)，即这棵子树内点数的两倍加 \(1\)。
即 \(r-l+1=\) 点数 \(\times2+1\)，算上 \(a_l\) 点数就是 \(\frac{r-l}2+1\)。
- 所有满足 \(a_l=a_r\) 的 \([l,r]\) 两两要么包含，要么不相交。
这个很好理解，因为是一棵树。现在对于残余的欧拉序列，我们递归地构造 \([l,r]\)：
- 对于 \([l',r']\subseteq[l,r],a_{l'}=a_{r'}\) 的 \([l',r']\) 递归处理，然后缩成一个点，表示把这棵子树看作一个点。
现在 \([l,r]\) 内没有相等的数了（除了 \(a_l,a_r\)）。求一下区间内不同的数数量 \(cnt\)，以及缩完点后序列长度 \(len\)。如果 \(cnt>\frac{len+1}2\) 则无解，否则我们将 \(\frac{len+1}2-cnt\) 种没出现过的数依次从左到右填在 \(0\) 的位置。
现在满足了 \(\frac{r-l+2}2\) 种不同的权值的条件。然后考虑从左到右补充序列：
对于每段形如 xy0 或者 0yx 的小段，我们可以将其补充为 xyx，然后缩成一个点 x。
手玩一下可以发现每次都能找到这样的小段，直到不存在两个相邻的 \(0\)。
最后只剩一些 \(0\) 的时候我们填上 \(a_l\) 即可。
链表实现合并，复杂度线性。
NOIP2023模拟测试赛（十）
A
B
建立 SAM，对于每个节点代表的所有字符串求有多少个满足条件。
是否满足条件等价于删去头一个字符，在末尾接上，看看是否在原串中出现。
由于 SAM 的优秀性质，直接走一个转移边如果能走到说明存在。
假设一个节点某一个 endpos 对应的左端点为 \([l,r]\)，注意到移位后的串左端点为 \([l+1,r+1]\) 所以跨到了下一个节点，还要看看 fa 是否有这个转移边。
复杂度 \(\mathcal O(n|\Sigma|)\)。
C
考虑序列版本P4331，做法是每次合并若干末尾段，直到中位数序列递增。
拓展到树上，改维护若干个段为维护若干连通块，每次加入一个点看看能不能与与其相邻的，权值最大的连通块合并。维护这些与其联通的连通块可以用平衡树 / 可并堆维护。
还要维护每个连通块的中位数。对顶堆 / 平衡树等。
复杂度视实现一个 \(\log\) 或者两个 \(\log\)。
据说是保序回归模板题。这下小丑了，改天学一下。
NOIP2023模拟测试赛（十一）
A
求出哪些割点把 \(s,t\) 割开。直接从 \(s\) 开始搜，要求 \(t\) 在割点割开的子树内即可。
B
原来是套路题。对于每一种方案，可以通过走两次与 \(2\) 相邻的边，即 \(d_{12}\) 或 \(d_{23}\) 得到权值加两倍边权的方案。
假设 \(p=2d_{12}\)。那么如果有一个方案，权值为 \(w\)，我们可以得到任何 \(w+kp\) 的方案。
那么，求一下 \(dis_{i,j}\) 表示从 \(2\) 走到 \(i\)，此时权值模 \(p\) 余 \(j\) 的最小权值。
如果 \(dis_{i,j}\) 已经 \(\ge k\)，那么再加 \(p\) 不会更接近 \(k\)。
否则我们可以加若干个 \(p\) 使得它最接近 \(k\)。这个是容易算的，现在只需要求 \(dis\) 即可。
把每个点拆成 \(p\) 个点，四条边拆成若干条边，跑一下最短路即可。
使用迪杰斯特拉，复杂度 \(\mathcal O(d\log d)\)。
C
只有前最多 \(60\) 次操作是有效的，因为查询的 \(l,r\le10^{18}\)。
每次要求 \(s_{1\sim x}\) 的某个字符出现次数。考虑求出最大的 \(k\) 满足操作完 \(k\) 次后序列长度小于 \(x\)。
即，\(2^k|s| < x \le2^{k+1}|s|\)。讨论一下 \(x\) 在被移位的段内还是段外，这个段的长度 \(\le100\) 可以直接预处理，这部分答案也可以预处理。
左边 \(2^k|s|\) 的串的答案很容易算，拿原串中出现次数乘上 \(2^k\) 即可。
而如果 \(x\) 在移位段的右侧，可以在前面找到与其相同的一段，递归处理。
复杂度应该是 \(\mathcal O(m\log V)\)。
NOIP2023模拟测试赛（十二）
A
dp，设 \(dp_{0/1}\) 为以 \(0/1\) 结尾的子序列个数。
转移方程显然是 \(dp_{a_i}\gets dp_0+dp_1+1\)。
到序列上，考虑矩乘，有：
\[\begin{bmatrix} dp_0&dp_1&1 \end{bmatrix} \times \begin{bmatrix} 1&a_i&0\\ 1-a_i&1&0\\ 1-a_i&a_i&1\\ \end{bmatrix} = \begin{bmatrix} dp'_0&dp'_1&1 \end{bmatrix}\]维护一下矩阵乘积以及反转后的乘积，区间反转直接交换两个乘积即可。
复杂度 \(\mathcal O(n\log n)\)，如果视矩乘复杂度为常数。
B
考虑二分时间 \(t\)，看是否每个点在这个时间后都至少被权值更大的点经过。
考虑两个点 \(i,j\)，若 \(d_i<d_j\)，则 \(i,j\) 在 \(t\) 时刻已经相遇等价于：
- \(d_i+v_it\ge d_j+v_jt\) 或者 \(d_i+v_it\le d_j+v_jt-L\)。
还有 \(w\) 的限制，考虑分治，先按 \(d\) 排序，分治中将左区间，右区间都按 \(w\) 排序。
考虑右区间对左区间的贡献。由于有 \(w\) 的限制，双指针扫一下最大的位置 \(p\) 满足 \(mid+1\sim p\) 的 \(w\) 都大于 \(w_i\)。
然后要求 \(mid+1\sim p\) 是否存在 \(j\) 满足 \(d_i+v_it\ge d_j+v_jt\) 或者 \(d_i+v_it\le d_j+v_jt-L\)。显然直接维护这些 \(j\) 的这些值的最大值、最小值，判断一下即可。
左边对右边的贡献是类似的，只不过 \(-L\) 移项变成 \(+L\)。复杂度 \(\mathcal O(n\log^2n)\)。
C
题意即求保留权值在 \([l,r]\) 中的边，求最小生成森林的权值。
考虑 lct，将边权从小到大排序，（边权转点权）加边时如果已联通则求出路径上的最小权值，设为 \(mn\)。
设当前权值为 \(w\)。则如果询问的 \(l\in(mn,w]\) 且 \(r\ge w\)，则这条边会在生成森林中。
由于强制在线，考虑主席树，在 \(w\) 版本的树上将 \((mn,w]\) 加 \(w\)，查询时查询 \(r\) 版本的树的 \(l\) 点处权值即可。
区间加还要打标记，恶心。差分转成单点加。
复杂度 \(\mathcal O(n\log n)\)。
NOIP2023模拟测试赛（十三）
A
求最大匹配可以树形 dp，具体地，设 \(f_{u,0/1}\) 表示 \(u\) 的子树内，\(u\) 是否被匹配的最大匹配数。
转移，\(f_{u,0}\gets \sum_{v}\max\{f_{v,0},f_{v,1}\}\)。
\(f_{u,1}\gets \max_v\{f_{v,0}+1+\sum_{w\not=v}\max\{f_{w,0},f_{w,1}\}\}\)。
手玩一下会发现一个性质：\(f_{u,1}-f_{u,0}\in[0,1]\)。
这个可以归纳：假设 \(v,w\) 满足条件，设 \(\Delta f_u=f_{u,1}-f_{u,0}\)。则
\[f_{u,0}\gets \sum_{v}f_{v,1} \]\[f_{u,1}\gets \max_v\{f_{v,0}+1+\sum_{w\not=v}f_{w,1}\}=\sum_{w}f_{w,1}+\max_v\{1-\Delta f_v\} \]\[\Delta f_u=\max_v\{1-\Delta f_v\} \]证毕。这里我们可以看到，若 \(\Delta f_v\) 存在一个 \(0\) 则 \(\Delta f_u\) 为 \(1\) 否则为 \(0\)。
现在设 \(F_{u,i,0/1}\) 为 \(u\) 的子树内，\(f_{u,1}\bmod m=i\) 且 \(\Delta f_u=0/1\) 的割边方案数。
对于每个儿子 \(v\)，合并先前的 \(F_u\) 和 \(F_v\)。具体地，考虑 \(u,v\) 间的边是否割去：
\[F'_{u,i,0}\gets \sum_{x+y\equiv i}F_{u,x,0}(F_{v,y,0}+F_{v,y,1})+\sum_{x+y\equiv i}F_{u,x,0}F_{v,y,1} \]第一个 \(\Sigma\) 表示割掉这条边的方案，既然割掉了，\(v\) 的 \(\Delta f\) 是无所谓的。当然这里先前的 \(\Delta f_u\) 得是 \(0\)。
第二个 \(\Sigma\) 表示不割这条边。那么由于合并完 \(\Delta f_u=0\)，则 \(\Delta f_v\) 不能有 \(0\)，只能从 \(F_{v,y,1}\) 转移。
\[F'_{u,i,1}\gets \sum_{x+y\equiv i}F_{u,x,1}(F_{v,y,0}+F_{v,y,1})+\sum_{x+y\equiv i}F_{u,x,1}(F_{v,y,0}+F_{v,y,1})+\sum_{x+y+1\equiv i}F_{u,x,0}F_{v,y,0} \]第一个 \(\Sigma\) 表示割掉这条边的方案。
第二个 \(\Sigma\) 表示不割掉这条边，且原先 \(\Delta f_u=1\) 的方案。既然 \(\Delta f_u\) 已经是 \(1\) 了也就不用管 \(\Delta f_v\) 了。
第二个 \(\Sigma\) 表示不割掉这条边，且原先 \(\Delta f_u=0\) 的方案。\(\Delta f_u\) 从 \(0\) 变为 \(1\)，说明出现了一个 \(\Delta f_v=0\)。
这样转移复杂度是 \(\mathcal O(nm)\) 的，具体可以参考树上背包的复杂度证明。
B
假设只求左下角，求完了转个三次再求三次减去重复算的一点点部分即可。
对于左下角的一个障碍点 \((x,y)\)，所有其左下角的区域都是不可达的。
那么就是要求对于一个询问点，求其左下角的所有点的左下角区域的并的面积。
从下往上扫 \(y\)，考虑维护一个序列 \(a\)，每次遇到一个障碍点 \((x,y)\) 将 \(a_x\) 设为 \(y\)。
查询 \((x_0,y_0)\) 即为扫到 \(y_0\) 时求 \(a\) 的 \([1,x_0]\) 的所有位置的后缀 \(\max\) 之和。
这个可以用一个神奇的线段树维护。考虑对于线段树上的一个节点 \(x\)，实现 qv(x,v) 表示在 \(x\) 所代表的区间中，求每个位置的后缀最大值与 \(v\) 的 \(\max\) 之和。
即，将 \(\le v\) 的后缀最大值补成 \(v\) 然后求和。
如何实现？线段树把区间最大值也维护了，然后对 \(v\) 分类讨论：
-
若 \(mx_{rs}<v\)，则右区间会全部被补成 \(v\)。这时候
qv(x,v)=qv(ls,v)+v*(r-mid)。 -
若 \(mx_{rs}\ge v\)，则左区间没有一个数会被补成 \(v\)。
设 \(ans_x\) 表示节点 \(x\) 的后缀 \(\max\) 之和。则此时 qv(x,v)=ans[x]-ans[rs]+qv(rs,v)。
因此 qv 可以单次 \(\mathcal O(\log)\) 询问得到。用这个函数实现线段树的 push_up，则为 ans[x]=qv(ls,mx[rs])+ans[rs]。
单点修改直接修改，每次 push_up 是对数复杂度的，因此全部的复杂度为 \(\mathcal O(n\log^2n)\)。
C
假设求出了每个 \(K\) 对应的答案 \(F_K\)，由于这个问题是一个网络流模型问题，一定有 \(F_{K+1}-F_K>F_K-F_{K-1}\)。
即，若干个 \((K,F_K)\) 组成一个下凸壳。
对于凸壳上的每个点 \((K,F_K)\)，都存在至少一个斜率 \(d\) 满足斜率为 \(d\) 的直线与凸壳切于 \((K,F_K)\)。
我们二分这个斜率 \(d\)，则相切的点即为 \(F_K-Kd\) 最小的点。
注意到 \(F_K\) 中恰好有 \(K\) 条边，因此这个等价于把题目中所有边权减去 \(d\) 然后求最小权匹配。
现在的最小权匹配没有了选的边数限制，可以状压 \(\mathcal O(nm2^m)\) 求出答案。
然后我们得到答案选择的边数 \(K'\)，判断其是否大于 \(K\)。如果大于则说明这个斜率太大了。继续二分即可。
这类选 \(K\) 个最大，可以网络流建模（具有凹凸性）的问题，可以用类似的二分解决，被称为 wqs 二分。
复杂度 \(\mathcal O(nm2^m\log n)\)。
NOIP2023模拟测试赛（十四）
A
建模：每个小朋友 \(i\) 拆成 \(m\) 个点 \((i,1)\sim(i,m)\)。
-
源点连 \((i,1)\)，权值为 \(-\infty\)。
-
\(\forall j\in[1,m),(i,j)\) 连 \((i,j+1)\)，权值为 \(w_{i,j}\)。
-
\((i,m)\) 连汇点，权值为 \(w_{i,m}\)。
如果不考虑限制，求最大割即为答案。
最大割由于割掉的边数固定，我们可以将每条边权变为 \(V-w\)，\(V\) 为一个较大的数，最后再用 \(nV\) 减掉。
这里会发现割掉 \((i,j)\) 与 \((i,j+1)\) 之间的边等于第 \(i\) 个小朋友选了 \(j\) 颗糖果。
考虑限制 \((x,y,z)\)，要使 \(x-y\le z\) 即 \(y\ge x-z\)，对于每个点 \((x,j)\) 连出一条权值 \(-\infty\) 向 \((y,j-z)\) 的边。
这样如果 \(x\) 选了 \(j\) 个糖果即割断了 \((x,j)\to(x,j+1)\)，必须要求 \(y\) 割的边在 \((y,j-z)\) 之后。
否则，存在一条路径 \(s\to(x,j)\to(y,j-z)\to t\)。
这样再求最大割即可。
B
直接模拟，每次撞车一定是两个 \(d\) 相邻的人撞在一起。
相邻的塞进优先队列，按撞车时间排序，每次删除一个点加进一组相邻的，用链表维护一下相邻的点。
注意删点时会删掉两组相邻的点，第一组即为队列顶部的，第二组可能还在队列里面，要惰性删除一下。
复杂度线性对数。
C
考虑每行求 \(\text{EGF}\)，全部乘起来，各项乘上 \(i!\) 之和即为答案。单点修改直接重新算这一行的 \(\text{EGF}\)。
每次都 NTT 再 INTT 是不行的，NTT 完直接把每一列此位置相乘，累加到答案数组中，最后再 INTT。
复杂度，多项式次数是 \(\mathcal O(nk)\) 的，每次修改 NTT 一次，累乘一次，复杂度即 \(\mathcal O(nmk\log(nk)+nmk^2)\)。
NOIP2023模拟测试赛（十五）
A
状压，如果求出了 \(f(S)\) 表示从 \(1\) 开始遍历集合 \(S\) 中的所有点所需最小时间，\(\min_S\{\max\{f(S),f(U-S)\}\}\) 即为答案，其中 \(U\) 表示包括所有点的全集。
\(f\) 如何求？设 \(dp_{S,i}\) 表示从 \(1\) 开始遍历了 \(S\) 中所有点，最后走到了 \(i\) 的最小时间。
那么每次转移枚举一个新点加进去，预处理一下最短路即可。
至于求方案，预处理最短路时求一下前驱节点即可。
复杂度 \(\mathcal O(n^22^n)\)。
B
\((i,p_i)\) 覆盖了一个区间，转化成对差分数组的加 \(1\) 减 \(1\)。
由于是一个排列，每个 \(i\) 一定出现在两个区间的左端点或者右端点中。
如果是两个左端点，这里差分的值就是 \(-2\)。如果是一左一右，就是 \(0\)；两个右端点就是 \(2\)。
现在来构造，首先如果：
-
全部的和不为零，则无解。
-
每一项不是 \(\pm2\) 也不是 \(0\)，无解。
-
存在一个前缀位置满足前缀和 \(<0\)，无解。（类似括号串）。
那么让 \(0\) 自己和自己匹配，\(2\) 和前面的 \(-2\) 匹配，栈维护一下即可。
C
把点坐标减 \(1\)，点编号减一，变为 \(0\sim n-1\)。
设 \(a_i^{(k)}\) 表示经过 \(k\) 次操作后的 \(a_i\) 的值。则 \(a_i^{(k)}\equiv2a_{(i+1)\bmod n}^{(k-1)}-a_i^{(k-1)}\pmod{m}\)。
那么会发现这个数可以用若干个原先的 \(a\) 叠加系数相加得到。
设 \(a_i^{(k)}\equiv\sum_{j=0}^{n-1}b_j^{(k)}a_{(i+j)\bmod n}^{(0)}\)，即 \(b_j^{(k)}\) 表示 \(k\) 次操作后 \(a\) 向后走 \(j\) 步对应在原序列中的系数。
容易发现这里 \(b\) 与 \(i\) 是无关的，即对于环上每个位置相对的系数都是不变的。（可以手玩一下）
对 \(a\) 有
\[\begin{aligned} a_i^{(k)} &\equiv2a_{i+1}^{(k-1)}-a_i^{(k-1)}\\ &\equiv2\sum_{j=0}^{n-1}b_j^{(k-1)}a_{(i+j+1)\bmod n}^{(0)}-\sum_{j=0}^{n-1}b_j^{(k-1)}a_{(i+j)\bmod n}^{(0)}\\ &\equiv2\sum_{j=0}^{n-1}b_{(j-1+n)\bmod n}^{(k-1)}a_{(i+j)\bmod n}^{(0)}-\sum_{j=0}^{n-1}b_j^{(k-1)}a_{(i+j)\bmod n}^{(0)}\\ &\equiv\sum_{j=0}^{n-1}(2b_{(j-1+n)\bmod n}^{(k-1)}-b_j^{(k-1)})a_{(i+j)\bmod n}^{(0)}\\ &\equiv\sum_{j=0}^{n-1}b_j^{(k)}a_{(i+j)\bmod n}^{(0)}\\ \end{aligned}\]所以 \(b_j^{(k)}=2b_{(j-1+n)\bmod n}^{(k-1)}-b_j^{(k-1)}\)。
设 \(B^{(k)}(x)=\sum_{i=0}^{n-1}b_{i}^{(k)}x^i\)。则显然有 \(B^{(k)}(x)=(2x+1)B^{(k-1)}(x)\)，这里卷积为循环卷积，即
\[[x^k](A\times B)=\sum_{(i+j)\bmod n=k}[x^i]A[x^j]B \]由于 \(B^{(0)}(x)=1\)，则 \(B^{(k)}(x)=(2x+1)^k\)，可以多项式快速幂。
最后对每个 \(i\) 要求 \(\sum_{j=0}^{n-1}b_j^{(t)}a_{(i+j)\bmod n}^{(0)}\)。这里发现 \(b,a^{(0)}\) 要取得下标差为 \(i\)，即为一个差卷积，翻转 \(a^{(0)}\) 卷一下即可。
这里模数是 \(m\)，但是每次卷积乘出来的数较小，可以卷积完直接取模。
复杂度 \(\mathcal O(n\log^2n)\)。