其实很简单（）
前置知识：FFT / NTT
001. P6800 【模板】CHIRP Z-TRANSFORM
> 给定一个 nnn 项多项式 P(x)P(x)P(x) 以及 c,mc, mc,m，请计算 P(c0),P(c1),…,P(cm−1)P(c^0),P(c^1),\dots,P(c^{m-1})P(c0),P(c1),…,P(cm−1)。所有答案都对 998244353998244353998244353 取模。
题解：
P(ci)P(c^i)P(ci) 的值为 ∑j=0n−1ajcij\sum\limits_{j=0}^{n-1}a_jc^{ij}j=0∑n−1 aj cij，因此要求的东西其实就是：
∀i∈[0,m),Fi=∑j=0n−1ajcij mod 998244353\forall i\in[0,m),F_i=\sum\limits_{j=0}^{n-1}a_jc^{ij}\bmod 998244353∀i∈[0,m),Fi =j=0∑n−1 aj cijmod998244353
这是一个二维卷积的形式，考虑使用 Chirp-Z Transform 优化。有核心公式：
ij=(i+j2)−(i2)−(j2)ij=\binom{i+j}2-\binom i2-\binom j2 ij=(2i+j )−(2i )−(2j )
用这个东西来替换上式的 ijijij，可得：
Fi=∑j=0n−1ajcij=∑j=0n−1ajc(i+j2)−(i2)−(j2)=c−(i2)∑j=0n−1ajc(i+j2)−(j2)=c−(i2)∑j=0n−1((ajc−(j2))(c(i+j2)))\begin{aligned} F_i&=\sum\limits_{j=0}^{n-1}a_jc^{ij}\\ &=\sum\limits_{j=0}^{n-1}a^jc^{\binom{i+j}2-\binom i2-\binom j2}\\ &=c^{-\binom i2}\sum\limits_{j=0}^{n-1}a^jc^{\binom{i+j}2-\binom j2}\\
&={\large{c^{-\binom i2}}}\sum\limits_{j=0}^{n-1}\left(\left(a^jc^{-\binom j2}\right)\left(c^\binom{i+j}2\right)\right) \end{aligned} Fi =j=0∑n−1 aj cij=j=0∑n−1 ajc(2i+j )−(2i )−(2j )=c−(2i )j=0∑n−1 ajc(2i+j )−(2j )=c−(2i )j=0∑n−1 ((ajc−(2j ))(c(2i+j )))
设 Ai=aic−(i2),Bi=c(i2)A_i=a_ic^{-\binom i2},B_i=c^{\binom i2}Ai =ai c−(2i ),Bi =c(2i )，那么上述式子形如一个等和卷积，翻转 BBB 得到 B′B'B′，设 C=A⊙BC=A\odot BC=A⊙B 即 AAA 和 BBB 的卷积，即可求得后半部分的和式。而前面的 c−(i2)c^{-\binom i2}c−(2i ) 可以单 log\loglog 计算也可以线性递推。总时间复杂度为 O(nlogn)O(n\log n)O(nlogn)，瓶颈在于 NTT。
我的实现细节处理的不怎么好，但是也能过（）
002. P14561 [CXOI2025] 我常常追忆过去
> 对于整数 nnn，有一张 nnn 个点的竞赛图，图上每一条边 (u,v)(u,v)(u,v)（u<vu<vu<v）的方向有 12\frac1221 的概率是由 uuu 连向 vvv 的，另外 12\frac1221 的概率是由 vvv 连向 uuu 的。
>
> 现在给定 mmm，对于每个 n=1…mn=1\ldots mn=1…m，你需要求出 nnn 个点的竞赛图上强连通分量的数目的期望，答案对 998244353998244353998244353 取模。
这么会夹带私货
首先先思考，假设给定了 nnn 的值，怎么快速计算答案。
容易证明若 A,BA,BA,B 两个点集之间，不存在任何一条边 u→vu\to vu→v 使得 u∈B,v∈Au\in B,v\in Au∈B,v∈A，那么 A,BA,BA,B 之间就形成了一个新的 SCC。
考虑直接计数这样被分割的 SCC 数量。考虑枚举集合 AAA 的大小 iii，那么有 (ni)\binom ni(in ) 种选择 AAA 的方法。定义 BBB 集合是 AAA 在全集下的补集，则若不存在 BBB 连向 AAA 的边，则两个点集之间的全部 2∣A∣×∣B∣2^{|A|\times|B|}2∣A∣×∣B∣ 条边都必须由 AAA 集合连向 BBB 集合即已被定向，因此答案即为 1+∑i=1n−1(ni)2−i(n−i)1+\sum\limits_{i=1}^{n-1}\binom ni2^{-i(n-i)}1+i=1∑n−1 (in )2−i(n−i)，简单细节处理或使用
O(n)−O(1)O(\sqrt n)-O(1)O(n )−O(1) 的光速幂均可做到 O(n)O(n)O(n) 计算答案。
然后考虑优化到快速计算 1∼n1\sim n1∼n 的答案。记竞赛图大小为 nnn 时的期望为 EnE_nEn ，则有：
En=1+∑i=1n−1(ni)2−i(n−i)=∑i=1n(ni)2−i(n−i)E_n=1+\sum\limits_{i=1}^{n-1}\binom ni2^{-i(n-i)}=\sum\limits_{i=1}^n\binom ni2^{-i(n-i)} En =1+i=1∑n−1 (in )2−i(n−i)=i=1∑n (in )2−i(n−i)
给这个东西搞一个 EGF 然后只保留系数，可以得到：
Enn!=∑i=1n2−i(n−i)i!(n−i)!\frac{E_n}{n!}=\sum\limits_{i=1}^n\frac{2^{-i(n-i)}}{i!(n-i)!} n!En =i=1∑n i!(n−i)!2−i(n−i)
记 p≡2−1(mod998244353)p\equiv 2^{-1}\pmod{998244353}p≡2−1(mod998244353)，则上式可以改写为：
Enn!=∑i=1npi(n−i)i!(n−i)!\frac{E_n}{n!}=\sum\limits_{i=1}^n\frac{p^{i(n-i)}}{i!(n-i)!} n!En =i=1∑n i!(n−i)!pi(n−i)
然后特殊处理掉边界上 i=0i=0i=0 的部分：
Enn!+1n!=∑i=0npi(n−i)i!(n−i)!\frac{E_n}{n!}+\frac1{n!}=\sum\limits_{i=0}^n\frac{p^{i(n-i)}}{i!(n-i)!} n!En +n!1 =i=0∑n i!(n−i)!pi(n−i)
这是一个二维卷积，可以用 Chirp-Z 变换和 NTT 将其优化至 O(nlogn)O(n\log n)O(nlogn) 求解。
具体而言：考虑经典套路，有 i(n−i)=(n2)−(i2)−(n−i2)i(n-i)=\binom n2-\binom i2-\binom{n-i}2i(n−i)=(2n )−(2i )−(2n−i )，于是开始推柿子：
∑i=0npi(n−i)i!(n−i)!=∑i=0np(n2)−(i2)−(n−i2)i!(n−i)!=∑i=0np(n2)×p−(i2)×p−(n−i2)i!(n−i)!=p(n2)∑i=0n(p−(i2)i!×p−(n−i2)(n−i)!)\begin{aligned} &\sum\limits_{i=0}^n\frac{p^{i(n-i)}}{i!(n-i)!}\\ =&\sum\limits_{i=0}^n\frac{p^{\binom n2-\binom i2-\binom{n-i}2}}{i!(n-i)!}\\
=&\sum\limits_{i=0}^n\frac{p^{\binom n2}\times p^{-\binom i2}\times p^{-\binom{n-i}2}}{i!(n-i)!}\\ =&p^{\binom n2}\sum\limits_{i=0}^n\left(\frac{p^{-\binom i2}}{i!}\times\frac{p^{-\binom{n-i}2}}{(n-i)!}\right)\\ \end{aligned} === i=0∑n i!(n−i)!pi(n−i) i=0∑n i!(n−i)!p(2n )−(2i )−(2n−i ) i=0∑n
i!(n−i)!p(2n )×p−(2i )×p−(2n−i ) p(2n )i=0∑n i!p−(2i ) ×(n−i)!p−(2n−i )
设 Ai=p−(i2)i!A_i=\dfrac{p^{-\binom i2}}{i!}Ai =i!p−(2i ) ，则设 C=A⊙AC=A\odot AC=A⊙A 即自己和自己的卷积，上述表达式的值可以记作 p(n2)Cnp^{\binom n2}C_np(2n )Cn 。因为 998244353998244353998244353 是 NTT 友好模数，所以可以 O(nlogn)O(n\log n)O(nlogn) 求解上述问题。
003. P5293 [HNOI2019] 白兔之舞
前置知识：矩阵优化 dp，单位根反演
先考虑 LLL 很小怎么做。容易想到枚举一共走了 iii 步，后面的方案数形如组合数乘以矩阵的形式。设转移矩阵为 MMM，则对于每个 t∈[0,k)∩Nt\in[0,k)\cap\mathbb Nt∈[0,k)∩N，答案可以表示为：
∑i≡t(modk)(Li)(Mi)x,y=∑i(Li)(Mi)x,y[i≡t mod k]=∑i(Li)(Mi)x,y[k∣i−t]=∑i[k∣i−t](Li)(Mi)x,y=∑i1k∑j=0k−1ωkj(i−t)(Li)(Mi)x,y=1k∑i∑j=0k−1ωkj(i−t)(Li)(Mi)x,y=1k∑i∑j=0k−1ωkij×ωk−tj(Li)(Mi)x,y=1k∑j=0k−1ωk−tj∑iωkij(Li)(Mi)x,y=1k∑j=0k−1ωk−tj∑i(Li)IL−iωkij(Mi)x,y=1k∑j=0k−1ωk−tj((I+ωkj×M)L)x,y\begin{aligned}
&\sum\limits_{i\equiv t\pmod k}\binom Li(M_i)_{x,y}\\ =&\sum\limits_i\binom Li(M_i)_{x,y}[i\equiv t\bmod k]\\ =&\sum\limits_i\binom Li(M_i)_{x,y}[k\mid i-t]\\ =&\sum\limits_i[k\mid i-t]\binom Li(M_i)_{x,y}\\ =&\sum\limits_i\frac1k\sum\limits_{j=0}^{k-1}\omega_k^{j(i-t)}\binom Li(M_i)_{x,y}\\
=&\frac1k\sum\limits_{i}\sum\limits_{j=0}^{k-1}\omega_k^{j(i-t)}\binom Li(M_i)_{x,y}\\ =&\frac1k\sum\limits_i\sum\limits_{j=0}^{k-1}\omega_k^{ij}\times\omega_k^{-tj}\binom Li(M_i)_{x,y}\\ =&\frac1k\sum\limits_{j=0}^{k-1}\omega_k^{-tj}\sum\limits_{i}\omega_k^{ij}\binom Li(M_i)_{x,y}\\
=&\frac1k\sum\limits_{j=0}^{k-1}\omega_k^{-tj}\sum\limits_i\binom Li\textrm{I}^{L-i}\omega_k^{ij}(M_i)_{x,y}\\ =&\frac 1k\sum\limits_{j=0}^{k-1}\omega_k^{-tj}((\textrm{I}+\omega_k^j\times M)^L)_{x,y} \end{aligned} ========= i≡t(modk)∑ (iL )(Mi )x,y i∑ (iL )(Mi )x,y [i≡tmodk]i∑ (iL )(Mi )x,y
[k∣i−t]i∑ [k∣i−t](iL )(Mi )x,y i∑ k1 j=0∑k−1 ωkj(i−t) (iL )(Mi )x,y k1 i∑ j=0∑k−1 ωkj(i−t) (iL )(Mi )x,y k1 i∑ j=0∑k−1 ωkij ×ωk−tj (iL )(Mi )x,y k1 j=0∑k−1 ωk−tj i∑ ωkij (iL )(Mi )x,y k1 j=0∑k−1 ωk−tj i∑ (iL )IL−iωkij (Mi )x,y k1 j=0∑k−1 ωk−tj ((I+ωkj ×M)L)x,y
把上述式子写成关于 ωkj\omega_k^jωkj 的函数，即设 f(x)=1k∑j=0k−1xj((I+ωkj×M)L)x,yf(x)=\frac 1k\sum\limits_{j=0}^{k-1}x^j((\mathrm{I}+\omega_k^j\times M)^L)_{x,y}f(x)=k1 j=0∑k−1 xj((I+ωkj ×M)L)x,y ，问题即为对每个 t∈[0,k)∩Nt\in[0,k)\cap\mathbb Nt∈[0,k)∩N 求 f(ωk−t)f(\omega_k^{-t})f(ωk−t ) 的值。注意到 f(x)f(x)f(x)
是一个多项式函数，而要求的值形如二维卷积的形式，因此可以使用 Chirp-Z Transform 优化。
因为这个题模数不固定，所以需要使用 MTT，这里使用了拆系数的 FFT 来计算答案（拆系数是因为卡精度）。因为这个题太卡精度了，所以这里使用了 long double。
004. CF1054H EPIC CONVOLUTION
咕咕咕，不知道什么时候能更新（）
