前言1：大佬们zc一下呗~
前言2：lyy还是太强了/bx
前置芝士：
代数基本定理：
1. 一个 ddd 次多项式可以被 d+1d+1d+1 个点唯一确定。
2. 还有要用的后面补吧
虚数，复数杂烩：
基础定义：i2=−1i^2=-1i2=−1。
复平面：想象一下，就是在一维实数轴上扩展一个虚数轴。
复数的表示：
1. 代数法：a+bia+bia+bi，其中 aaa 为实部，bibibi 为虚部，这个应该好理解。
2. 极角表示，想象一下，复平面上一个点到 OOO 为一个向量，其模长为 rrr，辐角为 θ\thetaθ，则可以表示为：r×cosθ+r×isinθr\times \cos\theta + r\times i\sin\thetar×cosθ+r×isinθ。
在复数计算上，加法就相当于向量相加，乘法相当于模长相乘，辐角相加，这在后面理解 FFT 有帮助。
欧拉公式
eiθ=cosθ+isinθe^{i\theta}=\cos\theta+i\sin\theta eiθ=cosθ+isinθ
还是从复平面的视角理解，物理意义就是当 θ∈[0,2π]\theta \in [0,2\pi]θ∈[0,2π]，eiθe^{i\theta}eiθ 刚好画出一个单位圆。
单位复数根
形如，求解一个方程：
zn=1z^n=1 zn=1
在实数域上只有 111（偶次方还有 −1-1−1），根据代数基本定理，在复数域上有 nnn 个根，我们怎么找这 nnn 个根？
既然 111 在复平面上是 (1,0)(1,0)(1,0)，对应着 2π2\pi2π 的整数倍，记为 2kπ2k\pi2kπ，对上面展开：
zn=ei2kπ ⟹ z=ei2kπnz^n=e^{i2k\pi} \implies z=e^{i\frac{2k\pi}{n}} zn=ei2kπ⟹z=ein2kπ
这 nnn 个根均匀分布在单位圆上，令逆时针第一个点为主 nnn 次单位根。 记为 ωn\omega_nωn 。 剩下的所有根都是 ωn\omega_nωn 多次旋转相同角度得到的，即：ωn0,ωn1,ωn2…ωnn−1\omega_n^0,\omega_n^1,\omega_n^2\dots\omega_n^{n-1}ωn0 ,ωn1 ,ωn2 …ωnn−1 。
一些引理
代数证明读者自证，应该挺简单的（？
1. 消去引理：
ωdndk=ωnk\omega_{dn}^{dk}=\omega_n^k ωdndk =ωnk
复平面上本质角度 θ\thetaθ 是不变的，所以它们也是相等的。
2. 折半引理
如果 nnn 是偶数，那么这 nnn 个单位根的平方，恰好对应 n2\frac{n}{2}2n 个 n2\frac{n}{2}2n 次单位根，每个出现 2 次。
为什么？ 想一想平方意味着什么？ 是不是角度相乘？
那么以 n=8n=8n=8 为例子，上下部分各 444 个点，平方后，上面 444 个点旋转到下面 444 个点的位置完全重合，下面同理，所以得证。 这是最核心的，是 FFT 能够做到 O(nlogn)O(n\log n)O(nlogn) 的原理。
3. 求和引理
∑j=0n−1(ωnk)j=0\sum_{j=0}^{n-1} (\omega_n^k)^j=0 j=0∑n−1 (ωnk )j=0
当然可以直接等比数列做，只是说需要证明其能作用在复数域上。 这里还是以复平面的视角看：
根据 nnn 次单位根的定义，nnn 个根构成了一个正 nnn 边形，把它们想象成 nnn 个与 OOO 构成的向量，因为它是一个完美对称的旋转体，所以向量和一定为 000。
拉格朗日插值
一般公式
已知 mmm 个点 (x1,y1),(x2,y2)…(xm,ym)(x_1,y_1),(x_2,y_2)\dots(x_m,y_m)(x1 ,y1 ),(x2 ,y2 )…(xm ,ym )（其中 xix_ixi 互不相同），寻找一个最高次数为 m−1m-1m−1 次的多项式 f(x)f(x)f(x) 使得：∀i,f(xi)=yi\forall i, f(x_i)=y_i∀i,f(xi )=yi 。
不考虑证明 （其实我不会），直接给出构造：
∑i=1myi×∏j≠ix−xjxi−xj\sum_{i=1}^{m}y_i\times \prod_{j \not= i} {\frac{x - x_j}{x_i - x_j}} i=1∑m yi ×j=i∏ xi −xj x−xj
感性的理解，就是只有当 x=xix=x_ix=xi 才有 yiy_iyi 的值，这么构造能完全满足所有条件。
有了这个，就可以做模板题了：
拓展问题
例如：
定义函数 Sk(n)=∑i=1nikS_k(n)=\sum_{i=1}^{n} i^kSk (n)=∑i=1n ik，求 Sk(n)(modp)S_k(n) \pmod pSk (n)(modp) 的值，（其中 n≤1018,k≤106n\le 10^{18},k\le 10^6n≤1018,k≤106）。
设 f(n)=Sk(n)f(n)=S_k(n)f(n)=Sk (n)，则前向差分 Δf(n)=f(n+1)−f(n)=(n+1)k\Delta f(n)=f(n + 1) - f(n) = (n + 1) ^ kΔf(n)=f(n+1)−f(n)=(n+1)k。
根据有限差分定理，既然 Δf(n)\Delta f(n)Δf(n) 为 kkk 次多项式，则 Sk(n)S_k(n)Sk (n) 为一个 k+1k+1k+1 次多项式。
根据前置芝士，我们知道需要 k+2k + 2k+2 个点来唯一确认这个多项式。
再看数据，显然 O(k2)O(k^2)O(k2) 做不了，需要优化。
回头看过程，我们发现点是可以自己取的，那我们可以取特殊点值来优化，例如：令 xi=ix_i=ixi =i。
代入原式：
∑i=1k+2yi×∏j≠in−ji−j\sum_{i=1}^{k+2}y_i\times \prod_{j \not= i} {\frac{n - j}{i - j}} i=1∑k+2 yi ×j=i∏ i−jn−j
考虑分母，分子分开优化：
* 分子：
∏j=1k+2n−jn−i\frac{\prod_{j=1}^{k+2}{n-j}}{n - i} n−i∏j=1k+2 n−j
为了避免出现 000 的情况，我们可以预处理前缀积与后缀积即可。
* 分母：
∏j=1,j≠ik+2i−j=(i−1)(i−2)…(1)×(i−(i+1))(i−(i+2))…(i−(k+2))=(i−1)!×(−1)k+2−i×(k+2−i)!\begin{aligned} \prod_{j=1,j\not=i}^{k+2}{i-j} &= (i-1)(i-2)\dots(1) \times (i-(i+1))(i-(i+2))\dots(i-(k+2))\\ &=(i-1)!\times (-1)^{k+2-i}\times (k+2-i)! \end{aligned} j=1,j=i∏k+2 i−j
=(i−1)(i−2)…(1)×(i−(i+1))(i−(i+2))…(i−(k+2))=(i−1)!×(−1)k+2−i×(k+2−i)!
显然这个可以用阶乘逆元处理。
但要注意，我们求插值是对一个前缀和求，所以我们构造的纵坐标是对 111 到 iii 的前缀 jkj^kjk 和。
P5364 [SNOI2017] 礼物
由题意得：
fi=fi−1+ik si=si−1+fi=2×si−1+ikf_i=f_{i-1}+i^k\ s_i=s_{i-1}+f_{i}=2\times s_{i-1}+i^k fi =fi−1 +ik si =si−1 +fi =2×si−1 +ik
求：sn=2×sn−1+nks_n=2\times s_{n-1}+n^ksn =2×sn−1 +nk。
注意到 nnn 很大，kkk 很小，而且这是一个递推式，考虑用矩阵加速优化。
考虑对后面的常数项进行二项式展开：
ik=((i−1)+1)k=∑j=0k(kj)×(i−1)ji^k=((i-1)+1)^k=\sum_{j=0}^{k}{\binom{k}{j}\times(i-1)^j} ik=((i−1)+1)k=j=0∑k (jk )×(i−1)j
所以，我们可以将 n0,n1,n2…nkn^0,n^1,n^2\dots n^kn0,n1,n2…nk 加入矩阵转移：
[sin0n1n2⋮nk]\begin{bmatrix} s_i\\ n^0\\ n^1\\ n^2\\ \vdots\\ n^k \end{bmatrix} si n0n1n2⋮nk
如何构造 basebasebase 辅助转移？ 考虑到转移后第 000 行 si+1=2×si+(i+1)ks_{i+1}=2\times s_i+(i+1)^ksi+1 =2×si +(i+1)k。
令 base0,0=2base_{0,0}=2base0,0 =2 且按照上面转化 ∀i∈[0,k],base0,i+1=(ki)\forall i \in [0,k], base_{0,i+1}=\binom{k}{i}∀i∈[0,k],base0,i+1 =(ik )，其余为 000。
对于 i∈[0,k]i\in [0,k]i∈[0,k]，有 (n+1)i=∑j=0i(ij)×nj(n+1)^i=\sum_{j=0}^{i}{\binom{i}{j}\times n^j}(n+1)i=∑j=0i (ji )×nj，所以：
令 basei+1,j+1=(ij)base_{i+1,j+1}=\binom{i}{j}basei+1,j+1 =(ji )，其余为 000。
最后就是矩阵快速幂和组合数的板子了。
FFT
这个玩意我觉得是学 NTT 和 FWT 的基础，它们本质几乎一样的，当然理解方法很多，这给出一种我觉得比较好理解的方法（？
先考虑一个问题：给定两个多项式 AAA 和 BBB 让你求其卷积，即求 C=A∗BC=A*BC=A∗B。
显然如果我们暴力按照系数去每位相乘是 O(n2)O(n^2)O(n2) 的。 这时 FFT 的思想就是将其转化为点值表达式对应相乘再还原。
形式化的讲，找一个 n×nn\times nn×n 的可逆变换矩阵 MMM，使得：
MC=(MA∘MB)M_C=(M_A \circ M_B) MC =(MA ∘MB )
这样的话，C=M−1(MA∘MB)C=M^{-1}(M_A \circ M_B)C=M−1(MA ∘MB )。
那 FFT 怎么处理的呢？
FFT 将变换空间引入到复数域，利用 nnn 次单位根的性质，分治求出点值，以达到快速求解。
具体怎么求点值？ 举一个例子：我们有一个次数界为 nnn 的多项式 AAA，表示为 A(x)=a0+a1x+a2x2+…an−1xn−1A(x)=a_0+a_1x+a_2x^2+\dots a_{n-1}x^{n-1}A(x)=a0 +a1 x+a2 x2+…an−1 xn−1，求出 nnn 个单位复数根。
这时绝妙的点来了！ 将其拆成奇数次项与偶数次项组成的多项式：
A[0](x)=a0+a2x+…A[1](x)=a1+a3x+…A^{[0]}(x)=a_0+a_2x+\dots\\ A^{[1]}(x)=a_1+a_3x+\dots A[0](x)=a0 +a2 x+…A[1](x)=a1 +a3 x+…
于是我们可以重组原多项式：A(x)=A[0](x2)+x×A[1](x2)A(x)=A^{[0]}(x^2)+x\times A^{[1]}(x^2)A(x)=A[0](x2)+x×A[1](x2)。
现在我们需要求解原多项式前半段 ωnk\omega_n^kωnk 和后半段 ωnk+n/2\omega_n^{k+n/2}ωnk+n/2 。
先求前半段（yky_kyk ）：
yk=A(ωnk)=A[0](ωn2k)+ωnkA[1](ωn2k)y_k=A(\omega_n^k)=A^{[0]}(\omega_{n}^{2k})+\omega_n^kA^{[1]}(\omega_{n}^{2k}) yk =A(ωnk )=A[0](ωn2k )+ωnk A[1](ωn2k )
根据折半引理：
yk=A[0](ωn/2k)+ωnkA[1](ωn/2k)y_k=A^{[0]}(\omega_{n/2}^{k})+\omega_n^kA^{[1]}(\omega_{n/2}^{k}) yk =A[0](ωn/2k )+ωnk A[1](ωn/2k )
再求后半段（yk+n/2y_{k+n/2}yk+n/2 ）：
yk+n/2=A(ωnk+n/2)=A[0](ωn2k+n)+ωnk+n/2A[1](ωn2k+n)y_{k+n/2}=A(\omega_n^{k+n/2})=A^{[0]}(\omega_{n}^{2k+n})+\omega_n^{k+n/2}A^{[1]}(\omega_{n}^{2k+n}) yk+n/2 =A(ωnk+n/2 )=A[0](ωn2k+n )+ωnk+n/2 A[1](ωn2k+n )
因为 ωnn=1\omega_n^n=1ωnn =1 且 ωnn/2=−1\omega_n^{n/2}=-1ωnn/2 =−1，代入得：
yk+n/2=A[0](ωn/2k)−ωnkA[1](ωn/2k)y_{k+n/2}=A^{[0]}(\omega_{n/2}^{k})-\omega_n^kA^{[1]}(\omega_{n/2}^{k}) yk+n/2 =A[0](ωn/2k )−ωnk A[1](ωn/2k )
这时观察两个式子，本质差别就在正负号上！ 这说明只要我们把子问题求出即可求出原问题。
合并就是著名的蝴蝶操作：
有了：
yk[0]=A[0](ωn/2k)yk[1]=A[1](ωn/2k)y_k^{[0]}=A^{[0]}(\omega_{n/2}^k)\\ y_k^{[1]}=A^{[1]}(\omega_{n/2}^k) yk[0] =A[0](ωn/2k )yk[1] =A[1](ωn/2k )
即可：
yk=yk[0]+ωnkyk[1]yk+n/2=yk[0]−ωnkyk[1]y_k=y_k^{[0]}+\omega_n^{k}y_k^{[1]}\\ y_{k+n/2}=y_k^{[0]}-\omega_n^{k}y_k^{[1]} yk =yk[0] +ωnk yk[1] yk+n/2 =yk[0] −ωnk yk[1]
可以结合图来理解。 应该是长得像蝴蝶所以叫蝴蝶操作？
现在我们有一些点值，怎么做逆变换呢？
观察发现，FFT 的可逆变换矩阵 MMM 就是有名的范德蒙德矩阵 (Vn)j,k=ωnjk(V_n)_{j,k}=\omega_n^{jk}(Vn )j,k =ωnjk ，其逆矩阵 (Vn)j,k−1=1nωn−jk(V_n)^{-1}_{j,k}=\frac{1}{n}\omega_{n}^{-jk}(Vn )j,k−1 =n1 ωn−jk （显然还需要证明范德蒙德矩阵有逆矩阵，只需证明 det(Vn)\det(V_n)det(Vn ) 不为 000 即可）。
考虑证明，令 U=(Vn)−1U=(V_n)^{-1}U=(Vn )−1：
(VnU)j,k=∑m=0n−1(Vn)j,m×Um,k=1n∑m=0n−1ωnm(j−k)(V_nU)_{j,k}=\sum_{m=0}^{n-1}{(V_n)_{j,m}\times U_{m,k}}=\frac{1}{n}\sum_{m=0}^{n-1}\omega_n^{m(j-k)} (Vn U)j,k =m=0∑n−1 (Vn )j,m ×Um,k =n1 m=0∑n−1 ωnm(j−k)
所以当 j=kj=kj=k 时为 111，其余根据求和引理始终为 000。
这时我们就有了一个递归的写法了，求逆只需按照上面改一下即可。
当然实际上我们实现中并不会使用递归，常数大且容易爆栈。
这就要说到迭代实现 FFT 了
给一个例子：
观察最后一层我们所处理出来的最小子问题，若它们成为一个序列，与原序列二进制下标作对比：
a0a1a2a3a4a5a6a7id1: 000001010011100101110111a0,a4,a2,a6,a1,a5,a3,a7id2: 000100010110001101011111\begin{array}{rcccccccc} & a_0 & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 \\ \text{id1: } & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ & a_0, & a_4, & a_2, & a_6, & a_1, & a_5, & a_3, & a_7 \\
\text{id2: } & 000 & 100 & 010 & 110 & 001 & 101 & 011 & 111 \end{array} id1: id2: a0 000a0 ,000 a1 001a4 ,100 a2 010a2 ,010 a3 011a6 ,110 a4 100a1 ,001 a5 101a5 ,101 a6 110a3 ,011 a7 111a7 111
观察到二进制下标是反转的！ 所以我们 O(n)O(n)O(n) 按照底层样式排序，进行从低到高做 FFT。
大概长这样：
这样我们就学完 FFT 了！ 可以先做一道模板题。
还有一个高精度乘法的问题，其实就是这个的延伸，只用最后处理一下进位和前导 000 即可。
NTT
因为 FFT 用到浮点数，可能在取模难处理或者求答案时会被挂精度，我们要找一个东西去完全替代 ωn\omega_nωn 。
这直接给结论：用原根代替。
考虑证明：
对于一个质数 ppp 和任意非零整数 aaa，有 gp−1≡1(modp)g^{p-1} \equiv 1 \pmod pgp−1≡1(modp) 且 p−1p-1p−1 是满足这个条件的最小正整数。
这样的话 ∀i∈[1,p−2],gi≢1(modp)\forall i \in [1,p-2],g^i \not \equiv 1 \pmod p∀i∈[1,p−2],gi≡1(modp)。
我们构造 NTT 单位根：
ωn≡gp−1n(modp)\omega_n \equiv g^{\frac{p-1}{n}} \pmod p ωn ≡gnp−1 (modp)
考虑是否满足三大引理：
1. 满足周期性 / 消去引理：(ωn)n=(gp−1n)n=gp−1≡1(modp)(\omega_n)^n=(g^{\frac{p-1}{n}})^n=g^{p-1} \equiv 1 \pmod p(ωn )n=(gnp−1 )n=gp−1≡1(modp)。
2. 满足折半引理：(ωnk+n2)2=ωn2k+n=ωn2k⋅ωnn≡ωn2k⋅1(modp)(\omega_n^{k+\frac{n}{2}})^2 = \omega_n^{2k+n} = \omega_n^{2k} \cdot \omega_n^n \equiv \omega_n^{2k} \cdot 1 \pmod p(ωnk+2n )2=ωn2k+n =ωn2k ⋅ωnn ≡ωn2k ⋅1(modp)。
3. 满足求和引理：∑j=0n−1(ωnk)j≡1−(ωnk)n1−ωnk(modp)\sum_{j=0}^{n-1} (\omega_n^k)^j \equiv \frac{1 - (\omega_n^k)^n}{1 - \omega_n^k} \pmod p∑j=0n−1 (ωnk )j≡1−ωnk 1−(ωnk )n (modp)。 其中分子 1−(ωnn)k≡1−1=0(modp)1 - (\omega_n^{n})^k \equiv 1 - 1 = 0 \pmod p1−(ωnn )k≡1−1=0(modp)，又因为 ggg 为原根，所以 1−ωnk≢1−1=0(modp)1 -
\omega_n^{k} \not\equiv 1 - 1 = 0 \pmod p1−ωnk ≡1−1=0(modp)，所以得证。
这样我们只用在 FFT 基础上套用原根即可（注意 NTT 对模数要求很苛刻，可以去搜一下）。
神级（秘）引用
分治 NTT 应用
套用 cdq 分治的思想，将前一半 NTT 先求出来，加入到右边去一起计算即可。
期望转化为系数
看了好几遍才看懂 QwQ。。
设 XXX 为我们抽取袜子的总次数，要找期望 E[X]E[X]E[X]。
常规定义是：E[X]=∑kk×P(X=k)E[X]=\sum_k{k\times P(X=k)}E[X]=∑k k×P(X=k)，这非常难算。
但是我们可以做一个转化，对于非负整数随机变量，有一个等价公式：
E[X]=∑k=0+∞P(X>k)E[X]=\sum_{k=0}^{+\infty} P(X>k) E[X]=k=0∑+∞ P(X>k)
意思是抽了 kkk 次还没结束，换句话讲就是前 kkk 次抽出来的袜子全是不同颜色。
那如何算 P(X>k)P(X>k)P(X>k) 的值？
假设有 S=∑AiS=\sum A_iS=∑Ai ，无顺序取出 kkk 只袜子，共有 (Sk)\binom{S}{k}(kS ) 种。
所以：P(X>k)=选出 k 只袜子颜色互不相同的方案数(Sk)P(X>k)=\frac{\text{选出 } k \text{ 只袜子颜色互不相同的方案数}}{\binom{S}{k}}P(X>k)=(kS )选出 k 只袜子颜色互不相同的方案数 。
那怎么求上面的东西？ 想象一下，对于第 iii 种袜子，我们要不拿一个（AiA_iAi 种可能），要不就不拿（111 种可能），所以单个 iii 的状态为：(1+Aix)(1+A_ix)(1+Ai x)。
所以 P(x)=∏i=1n(1+Aix)P(x)=\prod_{i=1}^n(1+A_ix)P(x)=∏i=1n (1+Ai x)。 暴力展开，对于第 kkk 次方的系数就代表着挑了 kkk 个 AixA_ixAi x 和 n−kn-kn−k 个 111，换句话讲就是从 nnn 种颜色里挑出 kkk 种不同的颜色的方案数！
所以记 xkx^kxk 的系数为 [xk]P(x)[x^k]P(x)[xk]P(x)，则：
E[X]=∑k=0n[xk]P(x)(Sk)E[X] = \sum_{k = 0}^{n} {\frac{[x^k]P(x)}{\binom{S}{k}}} E[X]=k=0∑n (kS )[xk]P(x)
所以我们只需用分治 NTT 求出 P(x)P(x)P(x) 每项系数，即可解决这道题！
FWT
本质上其实这玩意跟高维前缀和很像，因为位运算的性质以至于每一位互不影响，就像二维前缀和，我们可以对 iii 维先求再将求完的答案更新对 jjj 维再求一次即可（当然你也可以用克罗内克积和转移矩阵来理解，当然我是不会的）。
所以我们可以从一维开始考虑，以异或为例子：
给定 A=[A0,A1]A=[A_0,A_1]A=[A0 ,A1 ] 和 B=[B0,B1]B=[B_0,B_1]B=[B0 ,B1 ]，求异或卷积 C=A⊕BC=A \oplus BC=A⊕B。
根据异或规则：
C0=A0B0+A1B1C1=A0B1+A1B0C_0=A_0B_0+A_1B_1\\ C_1=A_0B_1+A_1B_0 C0 =A0 B0 +A1 B1 C1 =A0 B1 +A1 B0
跟上面类似，FWT 还是想处理出一个 A′A'A′ 和 B′B'B′ 使得 C′C'C′ 等于对应位置乘积。
那么就开始凑数（可以自己尝试一下相加，相减），这直接给结论：
A0′=A0+A1,B0′=B0+B1 ⟹ C0′=C0+C1A1′=A0−A1,B1′=B0−B1 ⟹ C1′=C0−C1A'_0=A_0+A_1,B'_0=B_0+B_1 \implies C'_0=C_0+C_1\\ A'_1=A_0-A_1,B'_1=B_0-B_1 \implies C'_1=C_0-C_1 A0′ =A0 +A1 ,B0′ =B0 +B1 ⟹C0′ =C0 +C1 A1′ =A0 −A1 ,B1′ =B0 −B1 ⟹C1′ =C0 −C1
逆变换也非常简单，已知 C0′=C0+C1C'_0=C_0+C_1C0′ =C0 +C1 和 C1′=C0−C1C'_1=C_0-C_1C1′ =C0 −C1 ，求 C0,C1C_0,C_1C0 ,C1 ，显然是一个二元一次方程组，随便解。
既然一维会了，有了上面的性质，就可以对整体进行分治，因为高 / 低位互相影响不到，我们可以从高位到低位进行分治：
假设数组长度为 444（下标 00,01,10,1100, 01, 10, 1100,01,10,11）：
1. 按最高位分治：最高位为 000 的一半是：A00,A01A_{00}, A_{01}A00 ,A01 （简称左半边）最高位为 111 的一半是：A10,A11A_{10}, A_{11}A10 ,A11 （简称右半边）。
因为最高位的异或不受低位影响，我们直接对这两半整体使用“魔法”：
新左半边 = 老左半边 + 老右半边。
新右半边 = 老左半边 - 老右半边。
2. 按次高位（最低位）分治：现在左右半边各自的内部，再根据次高位继续做同样的加减法。
AND 和 OR 的凑数比 XOR 简单，可以自己推一下。 （反正给代码）
这样就可以写模板了。 毕竟像我这么蒻的都能一次写对
FWT好题
看到 nnn 很小，考虑枚举行是否翻转的状态，通过神级观察（为什么都说很版啊，我蒻成区了），翻转任意行所对列产生的影响：翻转行的状态 iii ⊕\oplus⊕ 某个列状态 jjj。
这么看挺抽象的，举个例子就懂了，假设是行状态 i=101i=101i=101 即翻转第 000 行和第 111 行，某个列状态 j=110j=110j=110 那我们朴素翻转后 j→j′=011j \rightarrow j'=011j→j′=011，这时候再看上面结论，你会发现，i⊕j=011=j′i \oplus j=011=j'i⊕j=011=j′。
这下一切都简单了，令 AxA_xAx 为原始列向量的值，BxB_xBx 表示某个行状态所产生的最小贡献。
所以：
Ans(maski)=∑xAxBx⊕maskiAns(mask_i)=\sum_{x}{A_xB_{x \oplus mask_i}} Ans(maski )=x∑ Ax Bx⊕maski
转化一下式子：
Ans(maski)=∑x⊕y=maskiAxByAns(mask_i)=\sum_{x\oplus y=mask_i}{A_xB_y} Ans(maski )=x⊕y=maski ∑ Ax By
显然是一个FWT板子，这样就做完了。
给一道比较经典用FWT的树上异或Trick，祭奠我逝去的一整个下午。。。。
提示一下：题目可以转化为求满足条件路径异或和两个点的方案数。而图上异或路径有一个 Trick 就是，对于任意两个点 (u,v)(u,v)(u,v) 其异或路径为生成树上简单路径 + 任意环张成的线性空间。
