wyz 和她的故事

wangyizhi · 2025-07-17 22:10:41 · 休闲·娱乐

wyz 和她的故事。

防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透防剧透

前置知识

泰勒展开

广义二项式定理

其中实数的组合数通过下降幂定义。即

单位根

众所周知，n 次方程有 n 个根。所以方程 x^n=1 有 n 个根。

设 x = \cos\theta + i\sin\theta，则 x^n = \cos n\theta + i\sin n\theta = 1，所以 n\theta = 2k\pi，\theta = k\frac{2\pi}{n}。则第 k 个根为 x = \cos k\frac{2\pi}{n} + i\sin k\frac{2\pi}{n}。

记 \omega_n^k = \cos k\frac{2\pi}{n} + i\sin k\frac{2\pi}{n}，则 \omega_n^0 \sim \omega_n^{n-1} 就是一组单位根。但事实上我们也可能会用到 \omega_n^k(k\ge n) 的。

性质：

1. \omega_n^a\omega_n^b = \omega_n^{a+b}
2. (\omega_n^a)^b=\omega_n^{ab}
3. \omega_n^a=\omega_n^{a \bmod n}

单位根反演

证明：分类讨论

• 若 a \mid n，\omega_n^{ai} = 1，所以 右式 =1

• 若 a \nmid n，\omega_n^{a} \neq 1，使用等比数列求和公式，右式 =\frac{\omega_n^{an}-1}{\omega_n^a - 1}=0。

多项式

参考资料：https://www.luogu.com.cn/article/v7vgqau1

FFT

我们有两个多项式，显然它们的积可以用暴力方法计算，时间复杂度 O(n^2) 。但是，我们可以通过 快速傅里叶变换 降低其复杂度至 O(n \log n)。

多项式的积不好直接计算，但数值的积可以快速计算。因此我们要想方法把多项式转化成点值表示，这样把点值乘起来再逆变换回去就可以了。

那我们代入什么值呢？显然自然数不行。因为多项式多点求值在 我们还没发明出 FFT 暴力计算多项式乘法时都是 O(n^2) 的。但天才的傅里叶想到可以把单位根代入。那么问题就转化成了如何快速求出 F(x) 在 \omega_n^0,\omega_n^1,...,\omega_n^{n-1} 处的值。

这个显然不好直接计算，于是我们采用分治的思想。对于一个多项式 F(x)，我们把它分成两半，把次数为奇数的项和偶数的项分开，再提出一个 x，再换掉其中的 x^2。如 x^5+x^4+4x^3+5x^2+x+4=x^4+5x^2+4+x^5+4x^3+x=[(x^2)^2+5(x^2)+4]+x[(x^2)^2+4(x^2)+1]。于是我们可以得到两个新的多项式 G(x)，H(x)，使得 F(x)=G(x^2)+xH(x^2)。由于我们每次都要把它分成两半，不妨假设长度 n 为 2 的幂次。

那么假设我们已经求出 G(x) 和 H(x) 的点值表示了。不妨代入 \omega_n^k 与 \omega_n^{k+\frac{n}{2}}，那么我们可以得到

即

有了这两个式子，我们就可以快速求出点值了。这就是 离散快速傅里叶变换，简称 DFT。

分治的过程如图（来自 https://www.luogu.com.cn/article/v7vgqau1）：

时间复杂度显然 O(n \log n)。

然后考虑如何把点值转化回多项式。

假设序列 F 做 DFT 之后得到的序列为 G。则有 G_k=\sum_{i=0}^{n-1}(\omega_n^k)^i F_i。则有 F_k=\frac{1}{n}\sum_{i=0}^{n-1}(\omega_n^{-k})^i G_i。证明的话，代入然后等比数列求和分讨即可。

这就是 离散快速傅里叶变换的逆变换，简称 IDFT。

发现这个式子与原式只有单位根取了另一半，且最后除了个 n。因此写的时候可以封装在一起。

但先别急。容易发现这样常数很大，有没有什么快一点的方法呢？

注意到如果我们不递归实现，就可以减小很多常数。因此我们可以先把每一位交换到它最后会在的地方，然后向上归并实现。考虑每一位最后会到哪里。若当前最低位为 0，则变换后它会到前一半，否则会到后一半。显然就是 2 进制下翻转了一下。可以递推求出。然后我们只需枚举当前的区间长度（2,4,8,...），并枚举区间，用上面的式子计算就行了。

::::info[实现]

（嗯复数类啥的就不放了）

其中 sz 是大于卷积后式子长度的最小的 2 的幂。

for(int i=0;i<sz;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));

void FFT(compld *a,int n,int op)
{
    for(int i=0;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int mid=1;mid<n;mid<<=1)
    {
        compld omega(cos(PI/mid),op*sin(PI/mid));
        for(int len=mid<<1,i=0;i<n;i+=len)
        {
            compld o(1,0),x,y;
            for(int j=0;j<mid;j++,o=o*omega)
                x=a[i+j],y=o*a[i+j+mid],a[i+j]=x+y,a[i+j+mid]=x-y;
        }
    }
    if(op==-1) for(int i=0;i<n;i++) a[i].x=(int)(a[i].x/n+0.5);
}

FFT(a,sz,1),FFT(b,sz,1);
for(int i=0;i<sz;i++) a[i]*=b[i];
FFT(a,sz,-1);

::::

NTT

在大多数题目中，我们需要将结果取模，且需要避免浮点数运算。而且 FFT 常数较大，有没有快一点的方法呢？

当然是有的。但为了避免复数运算，我们需要在模意义下找到类似单位根的数。回想一下我们学过的数论知识，可以想到 原根。

原根 B 满足 B^k \equiv 1 \pmod p 且 k 最小。为了使原根能充当 FFT 用的单位根，我们需要让 k 是 2 的幂次且尽可能大。我们把这类模数称为 NTT 模数。比较常见的 NTT 模数有 998244353=7\times17\times2^{23}+1，最小原根为 3。

于是只要对上面的稍微改一下即可。

:::info[实现]

void ntt(int *a,int n,int op)
{
    for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int mid=1,len=2;mid<n;mid<<=1,len<<=1)
        for(int i=0,g=qpow(op>0?B:iB,(mod-1)/len);i<n;i+=len)
            for(int j=0,x,y,o=1;j<mid;j++,o=1ll*o*g%mod)
                x=a[i+j],y=1ll*o*a[i+j+mid]%mod,a[i+j]=rd(x+y),a[i+j+mid]=pr(x-y);
    if(op<0)
    {
        int iv=qpow(n,mod-2);
        for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv%mod;
    }
}

:::

MTT

有的时候模数不是 NTT 模数，那怎么办呢？

这时可以使用任意模数多项式乘法或三模 NTT。

三模 NTT 很简单，就是对三个 NTT 模数都做一遍 NTT 然后用 CRT 合并。

普通的任意模数多项式乘法（MTT）我不会。

多项式牛顿迭代

有函数 G(x,y)，求一多项式满足 G(x,f(x)) \equiv 0 \pmod{x^n}。

考虑倍增。在 n=1 时单独求出答案。下面讨论 n\ge 2 时的情况。

假设现在已经得到了模 x^{\lceil \frac{n}{2} \rceil} 意义下的解 f'。将 G(x,f(x)) 对 f(x) 在 f(x)=f'(x) 处泰勒展开，得

注意到 f(x)=f'(x) 时 f(x)-f'(x) 的最低次项次数为 \lceil \frac{n}{2} \rceil，所以对于 i>1，有 (f(x)-f'(x))^i \equiv 0 \pmod{x^n}。

所以有

因此

多项式乘法逆

使用多项式牛顿迭代。

设给的函数为 h(x)，则 G(x,y)=\frac{1}{y}-h(x)。所以有

另一种倍增法与牛顿迭代本质相同，不提。

时间复杂度均为 O(n \log n)

多项式 ln

设给定的函数为 f(x)。求 \ln f(x)。

考虑先求导然后积分。有

所以

因此

所以先求导，再求逆，然后乘法，最后积分即可。

时间复杂度为 O(n \log n)。

多项式 exp

有 O(n \log^2 n) 的分治 FFT 做法，但 我不会 有更优的做法，所以不讲。

考虑牛顿迭代。设给的函数为 h(x)，则 G(x,y)=\ln y-h(x)。所以有

时间复杂度 O(n \log n)。

多项式快速幂

一种朴素的想法是类似普通快速幂一样。时间复杂度 O(n \log n \log k)，其中 k 为次数。

如果多项式长度较小，那么可以做到时间复杂度为 O(\max(n,k) \log k)，但是一定要每次随着多项式长度改变卷积长度。

对于一般情况，由于

所以可以先做一次多项式 \ln，再做多项式 \exp，注意 k 在指数上是应模 \varphi(P)。时间复杂度 O(n \log n)。

多项式开方

一种思路是模仿多项式快速幂，有

多项式 \ln 后乘 \frac{1}{2} 再 \exp 即可。

也可以使用多项式牛顿迭代。设给的函数为 h(x)，则 G(x,y)=y^2-h(x)。所以有

时间复杂度均为 O(n \log n)。

分治 NTT

设有 n 个一次多项式，需要求出它们的乘积。朴素的暴力乘是 O(n^2) 的，但我们可以通过分治加速计算。

具体地，假设当前的分治区间为 [l,r]，将它分成 [l,m] 和 (m,r] 两个区间。假设两边的结果都已计算好，这时我们用 O((r-l+1) \log (r-l+1)) 多项式乘法合并两边的答案。

可以得到当问题规模为 n 时，时间复杂度为 T(n) = 2T(\frac{n}{2}) + O(n \log n)。得 T(n) = O(n \log^2 n)。

不会。

分治 NTT 一般是用来解决一些半在线卷积之类的。

对于分治区间，我们求出几个多项式表示分治区间对答案所造成的影响，然后向上合并。

看看例题吧。

P4721 【模板】分治 FFT

P9164 「INOH」Round 1 - 狂气

循环卷积

循环卷积是一个用于解决指数取模的小技巧。

P5224 Candies

::::info[problem]{open}

给定 n，m，k，求

• x+1
• x^2+x+1
• \sum_{i=0} x^{2i+1} = \frac{x}{1-x^2}
• \sum_{i=0} x^{4i} = \frac{1}{1-x^4}
• x^3+x^2+x+1
• x+1
• \sum_{i=0} x^{3i} = \frac{1}{1-x^3}

乘起来得到：

将除化为乘：

发现其等于选 4 个数使和等于 n-1 的个数。插板法可得答案为

::::

P2000 拯救世界

::::info[problem]{open}

为了拯救世界，小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。召唤出任何一位大神，都需要使用金木水火土五种神石。具体方法如下：

kkksc03 大神召唤方法： 金神石的块数必须是 6 的倍数； 木神石最多用 9 块； 水神石最多用 5 块； 火神石的块数必须是 4 的倍数； 土神石最多用 7 块。

lzn 大神召唤方法: 金神石的块数必须是 2 的倍数； 木神石最多用 1 块； 水神石的块数必须是 8 的倍数； 火神石的块数必须是 10 的倍数； 土神石最多用 3 块。

求用 n 块神石召唤两位大神的方案数。10^{99999}\leq n\lt 10^{100000}。

::::

::::info[solution]

列出每一位大神和每一种神石的 OGF，并乘起来：

化简得

即为

发现答案为将 n 划分成 5 个数的方案数。插板法得答案为

高精计算即可（乘法使用 NTT）。

::::

P4451 [国家集训队] 整数的lqp拆分

::::info[problem]{open}

求整数 n 的有序拆分方式的权值和。一种拆分 a_i 的权值为 \prod F_{a_i}，其中 F_n 表示斐波那契数列的第 n 项。

::::

::::info[solution]

选 1 个数时，答案的 OGF 为

考虑选 k 个数。此时答案的 OGF 为 F(x)^k。则选任意个数时，答案的 OGF 为

使沿用上边的方法，得到

所以答案为

注意到 \sqrt2 \equiv 59713600 \pmod {1000000007} 或 \sqrt2 \equiv 940286407 \pmod {1000000007}，直接计算即可。注意 n 对 \varphi(mod) 取模。

::::

EGF

定义数列 \{a_n\} 的 指数型生成函数 （EGF）为 \hat F(x)=\sum_{i=0} \frac{a_i}{i!}x^i。

EGF 有什么用呢？考虑如下问题：将 n 个有标号的球染成红色或蓝色，求方案数。

从生成函数的角度考虑。若其中有 i 个红球的方案数为 f_i，有 i 个蓝球的方案数为 g_i，则答案为

把组合数拆开（常用技巧）得：

假设答案为 h_n，则

所以！

由此例，我们可以发现 EGF 的一个重要性质：

因此我们借助 EGF 来较快地处理含有组合数特别是多重组合数的问题。

EGF exp 的组合意义

考虑有 n 个不同的球，把它们放入几个相同的盒子中。设 k 个球放入一个盒子中权值为 w_k，令 F(x) = \sum_{i=0} w_i x^i。

当放入 k 个盒子中时，考虑盒子顺序的方案数的 EGF 为 F(x)^k，但是盒子相同，所以方案数要除以 k!。所以答案的 EGF 为

由此我们可以得到 EGF exp 后的结果为元素构成集合的生成集族的权值之和。此处生成集的权值为其中所有集合元素的权值积。

::::warning[\exp(F(x)) 与 \frac{1}{1-F(x)} 的区别]

\gdef\isp{\text{ is prime}} \gdef\otw{\text{otherwise}} \gdef\eps{\epsilon}