多项式计数

注：其实前面还有一些内容，如矩阵树定理一类的东西。但是由于我还没有整理好所以把整俩好的部分弄上来。

一些 DFT / IDFT 的算法

学多项式是一个很有意思的过程。开始的时候你会学习 FFT / NTT 知道怎么样通过 DFT / IDFT 快速计算多项式的各种操作。然后你会深入学习多项式的各种运算，比如求逆、\(\exp,\ln\) 等等。然后你会到这一个部分，你发现又回到了 DFT / IDFT 的一些操作之中，但是再次看这些东西的时候，你其实比刚开始学的时候有了更为深入的理解。有一种“反其本矣”的奇妙感觉。

Bluestein

一般在做 DFT 的时候，会将给定的多项式变成 \(2^k\) 长度来操作，考虑这样一个问题：

给定 \(A(x)\)，求 \(A(x)\) 在 \(\omega^0,\dots,\omega^{n-1}\) 位置的点值。

转化，对于 \(b_0\dots b_{n-1}\)，令 \(b_m=\sum_{k=0}^{n-1}a_k\times (\omega^m)^k\)，有一个小技巧：

\[2mk=m^{\underline{2}}+(k-1)^{\underline{2}}-(m-k)^{\underline{2}} \]

通过这个来整理一下式子，能够得到：

\[b_m=\omega^{\frac{1}{2}m^{\underline{2}}}\sum_{k=0}^{n-1}a_k\omega^{\frac{1}{2}(k+1)^{\underline{2}}-\frac{1}{2}(m-k)^{\underline{2}}} \]

后面两个东西看起来很像一个卷积的形式，但是不标准，因为和事 \(m+1\)。经典平移一下，令 \(B_{m+n}=\omega^{-\frac{1}{2}m^{\underline{2}}}b_m\)，\(A_k=a_k\omega^{\frac{1}{2}(k+1)^{\underline{2}}}\)，再令 \(C_j=\omega{-\frac{1}{2}(j-n)^{\underline{2}}}\)，让 \(A_v=0,v\in[n,m+n]\) 能够得到：

\[B_{m+n}=\sum_{k=0}^{n+m}A_kC_{m+n-k} \]

这就是标准卷积形式，其中的 \(A,C\) 都是很好得到的。

注意在小技巧部分，如果用 \(2mk=m^2+k^2-(m-k)^2\) 看起来能够得到结果，但是这会导致 \(\sqrt{\omega}\) 的出现，这要求存在二次剩余。

Bluestein 还有一个优势就是可以做等比多点求值，且是 \(\mathcal{O}(n\log n)\)，比直接多项式多点求值要快。

I：JDU-4656

题面

给定 \(a,b,c,d\)，令 \(F(x)=\sum_{i=1}^{n-1}a_ix^{i}\)，\(\forall k\in[0,n)\) 求 \(F(b\times c^{2k}+d)\)。取模 \(10^6+3\)。

Sol

先推一下式子：

\[\begin{aligned} F(k)&=\sum_{i=1}^{n-1}a_i(b\times c^{2k}+d)^i\\ &=\sum_{i=1}^{n-1}a_i\sum_{j=0}^i\binom{i}{j}b^{j}c^{2kj}d^{i-j}\\ &=\sum_{j=0}^{n-1}\dfrac{b_jc^{2kj}}{j!}\sum_{i=j}^{n-1}\dfrac{i!a_id^{i-j}}{(i-j)!} \end{aligned} \]

令 \(p_j=\sum_{i=j}^na_ii!\dfrac{d^{i-j}}{(i-j)!}\)，这看起来就很能卷机的样子，搞一搞可以弄成：\(p'_{n-j}=\sum_{i=0}^{n-j}f_{n-i-j}g_i\) 的形式。

对于前面那个东西，回顾一下刚才的东西，令 \(\omega = c^{2k}\) 就是一个等比多点求值的过程了。

注意这题要 MTT。

单位根反演

核心式子：

\[[n|k]=\dfrac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik} \]

证明需要回顾一下单位根的性质，在多项式小记里面有，都是非常基础的。

• 如果 \(k\bmod n=0\)，此时有 \(\omega^{ik}=1\) 右边等于 \(\dfrac{1}{n}\times n=1\) 等于左边。
• 如果 \(k\bmod n \neq 0\)，此时右边是等比数列求和，结果为 \(\dfrac{\omega_n^{kn}-1}{\omega_n^k-1}\)，分子等于 \(0\) 且分母不等于 \(0\)。结果就是 \(0\)。

这个是处理形如“只保留某个数的倍数项”问题的利器。直接来看例题。

II：白兔的***难

题面

给定 \(n,k\) 求：

\[\forall0\le t<k,s_t=\sum_{i=-t}^{n-t}[k|i]\binom{n}{i+t} \]

\(n\le 10^{10^6},k=2^m,m\le 20\)。

Sol

进行单位根反演:

\[\begin{aligned} s_t&=\sum_{i=-t}^{n-t}[k|i]\binom{n}{i+t}\\ &=\sum_{i=-t}^{n-t}\dfrac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij}\binom{n}{i+t}\\ &=\dfrac{1}{k}\sum_{i=-t}^{n-t}\sum_{j=0}^{k-1}\omega_{k}^{ij}\binom{n}{i+t} \end{aligned} \]

套路地交换求和项，然后进行一些提取。

\[\begin{aligned} s_t&=\dfrac{1}{k}\sum_{j=0}^{k-1}\omega^{-tj}\sum_{i=-t}^{n-t}(\omega^{i+t})^{j}\binom{n}{i+t}\\ &=\dfrac{1}{k}\sum_{j=0}^{k-1}\omega^{-tj}\sum_{i=0}^{n}(\omega^{j})^{i}\binom{n}{i}\\ &=\dfrac{1}{k}\sum_{j=0}^{k-1}\omega^{-tj}(\omega^{j}+1)^n \end{aligned} \]

对于 DFT / IDFT 比较熟悉的选手能够看出来这部分就是一个 IDFT 过程（因为这刚好是一个 \(2^v\) 的多项式）就是我们在知道了点表示法然后转回到系数表示法的过程，这个在多项式小记里面也有式子。写起来是比较简单的。

来看一道综合一点的套路题，也是可爱的兔子。

III：白兔之舞

题面

给定 \((L+1)\times n\) 个点，可以理解为 \((L+1)\) 行 \(n\) 列。对于一对点 \((u_1,v_1),(u_2,v_2)\) 若 \(u_2>u_1\) 则 \((u_1,v_1)\to (u_2,v_2)\) 之间有 \(W[v_1][v_2]\) 条不同的边。其他情况没有边。现在给定 \(x,k,y\)，有一只兔子从 \((0,x)\) 开始，终点在 \((?,y)\)。对于所有 \(0\le t<k\)，求有多少条不同的路径满足其长度 \(len \bmod k=t\)，答案 \(\bmod p\)。

\(n\le 3,L\le 10^8,1\le k\le 65536,p\in prime,k|(p-1)\)。

Sol

先考虑固定长度 \(i\) 有多少种从 \((0,x)\to (?,y)\) 的方案，令这个问题答案为 \(f_i\)。对于行，相当于选择一些行去走，即 \(\binom{L}{i}\)，行和列是独立的，令 \(G\) 为开始时候的矩阵，那么列的情况就应该是 \(G\times W^i\) 的第 \(y\) 项，下面记为 \((G\times W^i)_y\)。经典传球问题。那么有 \(f_i=\binom{L}{i}\times (G\times W^i)_y\)，接下来就可以开始推式子了，令答案为 \(ans\)：

\[\begin{aligned} ans_t&=\sum_{i=0}^L[k|(i-t)]f_i\\ &=\sum_{i=0}^L\dfrac{1}{k}\sum_{j=0}^{k-1}\omega_k^{j(i-t)}\times \binom{L}{i}\times (G\times W^i)_y\\ &=(\dfrac{1}{k}\times \sum_{j=0}^{k-1}G\times \omega_k^{-jt}\sum_{i=0}^L(\omega_k^{j})^i\times \binom{L}{i}\times W^i)_y\\ &=(\dfrac{1}{k}\times \sum_{j=0}^{k-1}G\times \omega_k^{-jt}(\omega_{k}^j\times W+I)^L)_y \end{aligned} \]

这里已经看到胜利的曙光了，但是这个题有点问题在于并没有保证 \(L=2^v\) 不能走捷径，但是问题也不大，相当于要长度不为 \(2^v\) 的单位根的点值，老老实实用 Bluestein 做。但是还要注意要写 MTT，因为模数不确定。

感觉这题的评分点全在套路上了，推式子就是纯套路。

循环卷积

这部分的定义需要注意一下，不要和普通的线性卷积混淆。循环卷积如其名，为：

\[C_r=A(x)\otimes B(x)=\sum_{p,q}[(p+q)\bmod n=r]A_pB_q \]

我们一般写 DFT 的时候一般会有这样一步操作：

for(;n<sizX+sizY;n<<=1);

也就是说平时的时候我们做 DFT / IDFT 的时候实际上我们是取模了 \(2^v\)。但是有时候，题目会让我们去做一个 \(n\) 次意义下的循环卷积。你说，这很简单，我帮两个多项式乘起来，然后做一个 \(\mathcal{O}(n)\) 的加法实现循环卷积的功能。听起来很好，但是这个做法有不小隐患，来看一个例题。

IV：P4191

题面

给定两个 \(n\) 次多项式 \(A,B\)，和一个数字 \(c\)，求 \(A\times B^c\)，其中乘法的定义为 \(n\) 次循环卷积。取模 \(n+1\)，保证 \(n+1\) 是一个质数。

Sol

这时候上面 naive 的做法就不太行了，需要知道一个定理：

两个 \(n\) 次多项式的 \(n\) 次循环卷积等于他们 DFT 之后系数相乘再进行 IDFT 得到的结果。

这个定理在之前 FFT 的时候，我们是用“点表示法”来理解的。现在我们还可以用单位根反演来证明它，这里就先暂时略过。这个定理的用处在于，如果我们能够求出来 \(B\) 的 DFT 形式，对于每一个数做一次快速幂，然后做一次 IDFT 就可以得到 \(B^c\) 在 \(n\) 次意义下的循环卷积。

回顾我们在做 DFT 的时候要做什么，在 \(\omega^{0\to n-1}\) 的地方求点值。这时候我们 \(n\) 变得一般化了，这意味着要干什么？Bluestein 直接干就对了。

但是这个题目还有一个条件，保证输入的 \(n\) 能够分解成若干个不超过 \(\le 10\) 的数的乘积。运用这个条件，我们可以换一种方法试一试。

在正常的 FFT 中，我们有两个个关键的式子：

\(F(ω^{k+n/2}_n)=F_e(ω^{k}_{n/2})-ω^k_nF_o(ω^{k}_{n/2})\)

\(F(ω^k_n)=F_e(ω^k_{n/2})+ω^k_nF_o(ω^k_{n/2})\)

也就是说，我们通过把多项式分成奇偶两个部分，让两个部分分别只算 \(\frac{n}{2}\) 个点值，然后如此递归下去，最后只需要做若干个长度为 \(1\) 的多项式求一个点值。这样的复杂度就是 \(\mathcal{O}(n \log n)\)。

这个思想是可以推广的，对于一个普通的 \(n\)，如果其有因子 \(d\)，那么有仍然可以拆分成 \(d\) 个多项式求点值的结果，具体地：

\[A(\omega_n^j)=\sum_{i=0}^{d-1}\omega_n^{ij}A_i(\omega_{\frac{n}{d}}^j) \]

如果 \(n\) 是一个大质数，那么无法这样进行分解，只能做 \(n\) 次暴力点值，是非常糟糕的。但是由于 \(n\) 最大的质因子为 \(7\)，也就是说最后需要暴力做的长度最多是 \(7\)，就可以通过这个小技巧不用 Bluestein 的推导同样做出来。

例题

P3746

题面

求

\[(\sum_{i=0}^{\infty}\binom{nk}{ik+r})\bmod p \]

其中 \(n,k,r,p\) 给定 \(r<k\le 50,n\le 10^9\)，\(p\le 2^{30}\)。

Sol

如果你跟我一样一眼看不出答案就老老实实单位根反演，得到的结果是：

\[\dfrac{1}{k}\sum_{j=0}^{k-1}\omega_k^{-jr}(\omega_k^j+1)^{nk} \]

同样发现这是一个反演的式子，令 \(F_r\) 等于其，那么 \((1+ \omega_k^j)^{nk}\) 就是 \(F\) 在 \(\omega_k^j\) 位置的点值。也就是说 \(F_i=[x^i](1+x)^{nk}\) 注意这里应该是在 \(k\) 次意义下的循环卷积乘法，通过单位根的性质能够得到。需要特判 \(k=1\)，因为这时候 \((1+x)\) 本身就超过长度了，应该是 \(2\).

Loj6475

题面

给定 \(n,s,a_0,a_1,a_2,a_3\)，求：

\[(\sum_{i=0}^n\binom{n}{i}s^{i}a_{i\bmod 4})\bmod 998244353 \]

多测，\(T\le 10^5,n\le 10^{18},s,a\le 10^8\)。

Sol

显然要拆贡献，得到：

\[F_v=\dfrac{1}{4}a_v\sum_{j=0}^3\omega_4^{-jv}(s\omega_4^j)^n \]

注意到因为模数是给出来的，则 \(\omega_4^1=g^{\frac{p-1}{4}}\) 就有 \(\mathcal{O}(16\times T\log n)\) 的复杂度。

P5591

题面

求：

\[\sum_{i=0}^n \binom n i \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353 \]

其中 \(n,p\le 998244353,k\le 10^6,k=2^v\)。

Sol

这题需要一定的转化，向下取整式非常头疼的，向下取整在莫反里面用到的比较多，但这个题和数论函数关系不大。知道 \(\lfloor \frac{i}{k}\rfloor=\frac{i-i\bmod k}{k}\)，可以开始代换，我试了一下拆贡献，是可以做但是会让题目变得比较复杂，到后面要用白兔之舞的技巧，而且还需要稍微卡常，不拆贡献直接先一起考虑更好，对于后面需要取模的部分再拆贡献（需要用到：\(m\binom{n}{m}=n\binom{n-1}{m-1}\)

\[\begin{aligned} \sum_{i=0}^n\binom{n}{i}p^i\dfrac{i-i\bmod k}{k}&=\sum_{i=0}^n\binom{n}{i}p^i\dfrac{i}{k}-\sum_{i=0}^n\binom{n}{i}p^i\dfrac{i\bmod k}{k}\\ &=\dfrac{1}{k}\left( np(p+1)^{n-1} - \sum_{r=0}^{k-1}r[x^r](1+px)^n\right) \end{aligned} \]

后面的部分经典循环卷积，题目很善良地给了 \(k=2^v\)，因此直接做一次 NTT，然后每一个位置做一个 \(n\) 次幂，然后拉回来 \(\times r\) 即可。前面的更简单，直接数字运算。