FWT 集合幂级数

之前写的有点分散了，来个整合版。

FWT

带权前缀和

为了实现 FWT，我们需要实现所谓带权前缀和。

具体来说，给定序列 \(\{A\}_{i=0}^{c^n-1}\)（这里我们推广了一般的二进制情况），以及一个函数 \(w(i,j)\quad i \in [0,d^n),j\in [0,c^n)\)，我们需要求出：

\[\textup{FWT}(A)_i=\sum_{j}w(i,j)A_j \]

我们记 \(x^{(y)}_z\) 表示 \(x\) 在 \(y\) 进制下的第 \(z+1\) 位。

当上下文语意明确时，我们省略上标。

一般为了方便求解，\(w\) 有性质：

\[w(x,y)=\prod_{0\le i<n}w(x^{(d)}_i,y^{(c)}_i) \]

好的，怎么求解这个一般的 FWT 呢？

我们这里可以建出 \(c\) 进制的字典树，每一次我们维护子树内变换后的结果。

那么用转移的直接合并就可以了。

对于 \(c=d\) 的情况，可以原地非递归实现。

复杂度若 \(c=d\) 是 \(\Theta(nc^{n+1})\) 的，否则是 \(\Theta(c\sum_{0\le i<n}c^id^{n-i})=\Theta\left(cd^n\dfrac{1-(c/d)^n}{1-c/d}\right)\)。

我们一般认为 \(c,d\) 是常数，于是复杂度 \(\Theta(\max\{c,d\}^n)\)（如果 \(c\ne d\)。）

对于一般题目，你可以认为 \(c=d=2\)。

接下来考虑做卷积。

卷积

卷积就是给定两个序列 \(\{A_i\}_{i=0}^{c^n-1},\{B_i\}^{c^n-1}_{i=0}\)，以及 \(c\) 进制位运算 \(\textup{op}\)，求：

\[C_k=\sum_{i\textup{ op }j=k}A_iB_j \]

想要三个 \(\textup{FWT}\)，使得 \(C=\textup{FWT}_3(\textup{FWT}_1(A)\cdot \textup{FWT}_2(B))\)，这里 \(\cdot\) 表示对应相乘。

我们记三个 \(\textup{FWT}\) 的 \(w\) 分别为 \(w_1,w_2,w_3\)，再记 \(C_k=\sum_{i,j}w(k,i,j)A_iB_j\)。

那就是

\[C_k=\sum_{\mathscr{l}}w_3(k,\mathscr{l})\sum_{i,j}w_1(\mathscr{l},i)w_2(\mathscr{l},j)A_iB_j=\sum_{i,j}w(k,i,j)A_iB_j \]

也就是说

\[w(k,i,j)=\sum_{\mathscr{l}}w_3(k,\mathscr{l})w_1(\mathscr{l},i)w_2(\mathscr{l},j) \]

我们知道这些 \(w\) 每一位都是独立的，所以：

\[\begin{aligned} \prod_{p}w(k_p,i_p,j_p)=&\sum_{\mathscr{l}}\prod_{p}w_3(k_p,\mathscr{l}_p)w_1(\mathscr{l}_p,i_p)w_2(\mathscr{l}_p,j_p)\\ =&\prod_{p}\sum_{0\le \mathscr{l}_p<d}w_3(k_p,\mathscr{l}_p)w_1(\mathscr{l}_p,i_p)w_2(\mathscr{l}_p,j_p) \end{aligned} \]

第二步变换是因为 \(\mathscr{l}\) 恰好遍历了所有可能。

同时注意 \(\mathscr{l}\) 其实不一定是 \(c\) 进制的，这里我们设其为 \(d\) 进制。

于是

\[w(k_p,i_p,j_p)=\sum_{0\le \mathscr{l}<d}w_3(k_p,\mathscr{l})w_1(\mathscr{l},i_p)w_2(\mathscr{l},j_p) \]

这是什么？

我们记 \(\mathbf{W}^{(k)}_{i,j}=w(k,i,j),\lambda_{k,\mathscr{l}}=w_3(k,\mathscr{l}),\mathbf{V}^{(\mathscr{l})}_{i,j}=w_1(\mathscr{l},i)w_2(\mathscr{l},j)\quad 0\le i,j,k<c\quad 0\le \mathscr{l}<d\)。

那么就可以简单地写成：

\[\mathbf{W}^{(k)}=\sum_{\mathscr{l}}\lambda_{k,\mathscr{l}}\mathbf{V}^{(\mathscr{l})} \]

也就是说，给定 \(c\) 个 \(c\times c\) 矩阵。我们需要构造 \(d\) 个 \(c\times c\) 特殊的矩阵，使得给定的每个矩阵都可以表示为构造矩阵的线性组合。

你构造的矩阵应该可以被写成列向量和行向量的乘积，也就是说这些矩阵每行每列成比例（秩为 \(1\)），当然构造的矩阵越少越好。

这被称作张量分解。

只要知道张量分解，我们便能知道这三个 \(\textup{FWT}\) 变换分别是什么从而实现。

假设卷积是 \(c\) 进制的，你使用了 \(d\) 个矩阵，若 \(c\ne d\)，复杂度为 \(\mathcal{O}(\max\{c,d\}^n)\)，若 \(c=d\)，复杂度为 \(\mathcal{O}(nc^n)\)。

但是，最小张量分解是 NP-Hard 的，这使得 \(\textup{FWT}\) 很大程度上依赖于直觉（或者是超级暴力。）

符号声明：\(\subseteq\) 表示包含于，\(\subset\) 表示真包含于。

集合幂级数

我们令 \(U=\{0,\dots,n-1\}\)。

一个集合幂级数 \(f\) 是对于全集 \(U\) 和环 \(R\)，一个 \(2^U\to R\) 的映射，对于 \(S \subseteq U\)，记 \(f_{S}\) 表示 \(S\) 所对应的值。

通俗点说，就是长度为 \(2^n\) 的数组，标号从 \(0\) 开始。

这里可能有一个令人困惑的事情：集合幂级数中的究竟是集合还是数？在讨论位运算卷积时，我们更像是当作二进制数来对待。

在 OI 中，\(R\) 一般取对质数 \(P\) 取模的 \(\mathbb{F}_P\)。

也写作

\[f=\sum_{S \subseteq U}f_Sx^S \]

这里的 \(x^{S}\) 完全是形式记号，这个写法仿照了形式幂级数，但不应该看作一个关于 \(x\) 的函数。

运算

我们需要运算，首先和差加法逆是好定义的。

对于两个集合幂级数 \(f,g\)，定义它们的和 \(f+g\) 为

\[(f+g)_S=f_S+g_S \]

对于集合幂级数 \(f\)，定义加法逆 \(-f\) 为

\[(-f)_S=-f_S \]

对于集合幂级数 \(f,g\)，定义减法 \(f-g\) 为

\[(f-g)_S=f_S-g_S \]

接下来考虑两个集合幂级数的乘法，也就是卷积。

OR 卷积

我们知道，对于两数列 \(a,b\)，其卷积 \(a\ast b=c\) 为

\[c_i=\sum_{x+y=i}a_xb_y \]

这里我们可以把 \(x+y=i\) 看成一个抽象的形式，即对于任意二元函数 \(\operatorname{op}(x,y)\)，我们都可以定义

\[c_i=\sum_{\operatorname{op}(x,y)=i}a_xb_y \]

为 \(a,b\) 的某种卷积。

普通序列卷积中，这个运算是加法，对于集合我们尝试定义「加法」，考虑集合并。

\[(f\ast g)_S=\sum_{L \cup R=S}f_Lg_R \]

这就是集合并卷积，因为一般用二进制数表示集合，集合并就是 OR 运算，所以也称 OR 卷积。

当然也可以用 FWT 做。

求集合并卷积是简单的，可以考虑高维前缀和（这被称作快速莫比乌斯变换），定义 \(\operatorname{FMT}(f)_S=\sum_{T \subseteq S}f_T\)，不难有

\[\operatorname{FMT}(f\ast g)_S=\sum_{L \cup R\subseteq S}f_Lg_R=\sum_{L,R \subseteq S}f_Lg_R=\operatorname{FMT}(f)_S\operatorname{FMT}(g)_S \]

对于多个的 OR 卷积，容易发现可以先全部 FMT，乘起来后再逆 FMT。

对于逆 FMT，记作 \(\operatorname{FMT}^{-1}\)，我们要用到子集反演：

\[f_S=\sum_{T \subseteq S}(-1)^{|S|-|T|}\operatorname{FMT}(f)_T=(-1)^{|S|}\sum_{T\subseteq S}(-1)^{|T|}\operatorname{FMT}(f)_T \]

证明：

\[\begin{aligned} &\sum_{T \subseteq S}(-1)^{|S|-|T|}\operatorname{FMT}(f)_T\\ =&\sum_{T\subseteq S}(-1)^{|S|-|T|}\sum_{T^{\prime}\subseteq T}f_{T^{\prime}}\\ =&\sum_{T^{\prime}\subseteq S}f_{T^{\prime}}\sum_{T^{\prime}\subseteq T \subseteq S}(-1)^{|S|-|T|}\\ =&\sum_{T^{\prime}\subseteq S}f_{T^{\prime}}\sum_{i=0}^{|S|-|T^{\prime}|}(-1)^{|S|-|T^{\prime}|-i}\binom{|S|-|T^{\prime}|}{i}\\ =&\sum_{T^{\prime}\subseteq S}f_{T^{\prime}}(-1)^{|S|-|T^{\prime}|}[|S|=|T^{\prime}|]\\ =&f_S \end{aligned} \]

FMT 和 IFMT 实现：

typename<typename T>
void FMT(int n,T *a){for(int j=0;j<n;++j){for(int i=0;i<(1<<n);++i){if((i>>j)&1){a[i]+=a[i^(1<<j)];}}}
}
typename<typename T>
void IFMT(int n,T *a){for(int i=0;i<(1<<n);++i){a[i]=((__builtin_popcount(i)&1)?-a[i]:a[i]);}for(int j=0;j<n;++j){for(int i=0;i<(1<<n);++i){if((i>>j)&1){a[i]+=a[i^(1<<j)];}}}for(int i=0;i<(1<<n);++i){a[i]=((__builtin_popcount(i)&1)?-a[i]:a[i]);}
}

AND 卷积

把子集和改为超集和即可。

子集卷积（无交并卷积）

接下来是重要的子集卷积，我们定义

\[(f\times g)_S=\sum_{L \sqcup R=S}f_Lg_R=\sum_{T \subseteq S}f_Tg_{S\setminus T} \]

这里 \(\sqcup\) 意思是无交并。

这看起来比较困难，因为我们并不能通过一个简单的变换将其转化成逐位相乘。

但是注意到 \(L\sqcup R=S\Leftrightarrow L\cup R=S\land |L|+|R|=|S|\)，我们可以将 \(R\) 替换为 \(R[x]\)，对于 \(S\)，定义新的 \(f^{\prime}_S=f_S x^{|S|}\)。

那么我们可以对这样替换后的 \(f^{\prime},g^{\prime}\) 做一遍 OR 卷积，然后对于每个 \(S\)，只取 \(|S|\) 次的系数。

多项式乘法朴素实现是 \(n^2\) 的，于是复杂度 \(\Theta(n^22^n)\) 当然你也可以用 FFT，但是在 \(n\) 较小时常数是更劣的。

集合幂级数复合（exp，ln，求逆）

接下来我们定义 \(k\) 次幂为 \(f^k=\underbrace{f\times f \dots \times f}_{k \text{个} f}\)，对于一个形式幂级数 \(H(x)=\sum_{i \ge 0}h_ix^i\)，定义复合

\[H(f)=\sum_{i \ge 0}h_if^i \]

是一个集合幂级数。

我们令 \(f^{\prime}_S=f_Sx^{|S|},\overline{f}=\operatorname{FMT}(f^{\prime})\)，有

\[\overline{(f+g)}_S=\overline f_S+\overline g_S \]

\[(\overline{f\times g})_S=\overline f_S \cdot \overline g_S \]

这样就有 \(\overline{H(f)}_S=H(\overline{f}_S)\)。

我们可以先将 \(f\) 转成 \(\overline{f}\)，对于每一个 \(S\) 计算 \(g_S=H(\overline{f}_S)\)，省略 \(n\) 次以上的项，再得到 \([x^{|S|}]\operatorname{FMT}^{-1}(g)_S\)

根据最新科技，多项式复合在 \(\mathbb{F}_{998244353}\) 下可以做到 \(\Theta(n \log^2 n)\)，我们得到 \(\Theta(n \log^2 n 2^n)\) 的集合幂级数复合。

当然实际上用不着这个对于 \(h(x)=\exp(x)\) 和 \(\ln(1+x)\) 以及 \(\dfrac{1}{1-x}\) 的情况下，直接 \(\Theta(n^2)\) 求就可以了。

呃，怎么 \(\Theta(n^2)\) exp，ln，求逆？

如果你不知道什么是 exp，ln，求逆：

\[\exp(x)=\sum_{i \ge 0}\dfrac{x^i}{i!}=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\dots \]

\[\ln(1+x)=\sum_{n \ge 1}\dfrac{(-1)^{n+1}x^n}{n}=x-\dfrac{1}{2}x^2+\dfrac{1}{3}x^3-\dots \]

\[\dfrac{1}{1-x}=\sum_{n \ge 0}x^n \]

求逆

给你 \(A\)，要求

\[\sum_{i=0}^{n}A_iB_{n-i}=[n=0] \]

于是

\[A_0B_n=-\sum_{i=1}^{n}A_iB_{n-i} \]

\[B_n=-\dfrac{1}{A_0}\sum_{i=1}^{n}A_iB_{n-i} \]

\[B_0=\dfrac{1}{A_0} \]

ln

\(B(x)=\ln A(x)\)，于是 \(B^{\prime}(x)=\dfrac{A^{\prime}(x)}{A(x)}\)，可以直接求逆再积分。

但这样子常数太大，我们可以直接递推

\[B^{\prime}(x)A(x)=A^{\prime}(x) \]

\[(n+1)A_{n+1}=\sum_{i=0}^{n}(i+1)B_{i+1}A_{n-i}=(n+1)B_{n+1}+\sum_{i=0}^{n-1}(i+1)B_{i+1}A_{n-i} \]

\[B_{n+1}=\dfrac{(n+1)A_{n+1}-\sum_{i=1}^{n}iB_iA_{n+1-i}}{n+1} \]

\[B_{n}=A_n-\dfrac{\sum_{i=1}^{n-1}iB_iA_{n-i}}{n} \]

\[B_0=0 \]

exp

\(B(x)=\exp(A(X))\)，于是 \(B^{\prime}(x)=A^{\prime}(x)B(x)\)。

\[(n+1)B_{n+1}=\sum_{i=0}^{n}(i+1)A_{i+1}B_{n-i} \]

\[B_n=\dfrac{1}{n}\sum_{i=1}^{n}iA_{i}B_{n-i} \]

\[B_0=1 \]

部分 exp

我们定义 \(\exp_k(x)=\sum_{i=0}^{k}\dfrac{x^i}{i!}\)。

\[B(x)=\sum_{i=0}^{k}\dfrac{A(x)^i}{i!} \]

\[B^{\prime}(x)=\sum_{i=0}^k \dfrac{A^{\prime}(x)A(x)^{i-1}}{(i-1)!} \]

\[B^{\prime}(x)=A^{\prime}(x)(B(x)-\dfrac{A(x)^k}{k!}) \]

令 \(C(x)=\dfrac{A(x)^k}{k!}\)（不难直接求得）

\[(n+1)B_{n+1}=\sum_{i=0}^{n}(i+1)A_{i+1}(B_{n-i}-C_{n-i}) \]

\[B_{n}=\dfrac{1}{n}\sum_{i=1}^{n}iA_{i}(B_{n-i}-C_{n-i}) \]

\[B_0=1 \]

其中 exp 是有重要的组合意义的，其表示将一个集合无序拆分成若干子集，所有拆分方案的权值和。

你已经掌握了集合幂级数的基础知识，接下来是一些练习。

练习

CF1034E Little C Loves 3 III

给你一个 \(\{A_i\}_{i=0}^{2^n-1},\{B_i\}_{i=0}^{2^n-1}\)，求

\[C_i=\sum_{\begin{aligned}j\textup{ or }k=&i\\j\textup{ and }k=&0\end{aligned}}A_jB_k \]

模 \(\bm 4\) 意义下。

\[n\le 21 \]

做法

注意到 \(n\le 21\)，所以 \(\Theta(n^22^n)\) 的子集卷积过不了。

考虑子集卷积的本质，就是乘上一个形式变量 \(x\)：

\[\begin{aligned}A_i^{\prime}&=A_ix^{\textup{popcount}(i)}\\B_i^{\prime}&=B_ix^{\textup{popcount}(i)}\end{aligned} \]

但是我们真的需要维护一个次数为 \(n\) 的多项式乘法呢？

直接令 \(x=4\)，跑 OR 卷积再除以 \(4^{\textup{popcount}(i)}\)，最后对 \(4\) 取模，这样所有 \(j\textup{ and }k\ne 0\) 的都被消掉了。

由于 \(4^{21}\le 2^{64}\)，可以用 ULL 存。

这里当然会溢出，但是溢出的肯定没有贡献。

一般记 \(e(S)\) 表示在一个图中点集 \(S\) 的导出子图边数，\(e(S,T)\) 表示所有 \(u \in S,v\in T\) 的边 \((u,v)\) 数量（一般假设 \(S\cap T=\varnothing\)），在无向图中，有 \(e(S,T)=e(S\cup T)-e(S)-e(T)\)。

数 DAG 定向 CF1193A

给你一个有向图 \(G=(V,E)\)，你需要对一些边改变方向，使得定向后图为 DAG，求对于所有合法的定向方案改变的边数量之和。

保证两点之间最多一条边。（忽略方向）

做法

首先考虑对于一个改变边的方案 \(E^{\prime}\)，我们取其补集 \(E\setminus E^{\prime}\) 也可以得到一个合法方案，且改变边的数量和为 \(m\)。

将原图视为无向图，我们只需求出有多少种定向方案为 DAG 再乘上 \(\dfrac{m}{2}\) 即可。

令 \(f_S\) 表示将 \(S\) 的导出子图内所有边定向且为 DAG 的方案数。

考虑枚举出度为 \(0\) 的点集 \(T\)，首先 \(T\) 要为独立集，然后所有从 \(S\setminus T\) 到 \(T\) 的边的方向被唯一确定，似乎有

\[f_S=[S=\varnothing]+\sum_{T \subseteq S}[T\text{ 是独立集且非空}]f_{S\setminus T} \]

但这显然是错的，因为我们会重复计数，对于恰有 \(|\overline{T}|\) 个点为出度为 \(0\) 点的情况下，会被重复计数 \(2^{|\overline{T}|}-1\) 次。

考虑容斥，我们添加上容斥系数 \((-1)^{|T|-1}\)，这样因为

\[\sum_{\varnothing\subset T \subseteq \overline{T}}(-1)^{|T|-1}=[\overline{T}\ne \varnothing] \]

就恰被计算了一次。

这个技巧被称为 DAG 容斥。

这样朴素做是 \(\Theta(3^n)\) 的，可以通过，但利用集合幂级数可以做到更优的复杂度。

这个转移是半在线的，后面会讲如何做半在线子集卷积，但这里可以直接推式子。

我们记 \(g_S=[S\text{ 是独立集且非空}](-1)^{|S|-1}\) 那么有

\[f=1+f\times g \]

于是有 \(f=\dfrac{1}{1-g}\)，直接求逆即可。

数 DAG 生成子图

给你一个有向图，求有多少个生成子图是 DAG。

做法

和之前差不多，令 \(f_S\) 表示点集 \(S\) 以内的 DAG 生成子图数，枚举出度为 \(0\) 点，有转移：

\[f_S=\sum_{\varnothing\subset T\subseteq S} (-1)^{|T|-1}f_{S\setminus T}2^{E(S\setminus T,T)} \]

由于这里是有向边，所以只能 \(\Theta(3^n)\)。

数强连通 CTT2014 D1T2 主旋律

给你一个有向图，求边的子集强连通数量。

做法

考虑一个想法，用 \(2^m\) 减去所有有两个以上强连通分量的子图。

那么假设已经知道好了强连通分量的划分，那么内部就是强连通子图，外部就是 DAG 子图计数。

数连通生成子图

给你一个无向图 \(G=(V,E)\)，求连通生成子图数量。

做法

似乎并不好直接刻画连通性，但我们知道

\[\text{图}=\sum\text{连通块} \]

假设我们已经知道了对于点集 \(S\) 内部的连通生成子图数，令 \(g\) 表示 \(S\) 内部生成子图数，有

\[g=\exp f \]

反过来就有 \(f=\ln g\)，而 \(g_S=2^{e(S)}\)，直接做集合幂级数 ln 即可。

这里有一个启示，对于生成子图，我们一般考虑将其组合得到简单的，再反过来推导。

数连通二分生成子图 at_arc205_f

给你一个图 \(G=(V,E)\)，求有多少个连通的生成子图是二分图。

做法

注意到

\[\text{二分图且染色}=\sum \text{连通二分图且染色} \]

染色是为了保证只计数一次。

令 \(g_S\) 表示 \(S\) 以内二分生成子图且染色的方案数，\(f_S\) 表示 \(S\) 以内连通二分生成子图且染色的方案数，所求即 \(\dfrac{f_U}{2}\)。

\[g=\exp f \]

\[f=\ln g \]

考虑如何求 \(g\)。

有

\[g_S=\sum_{T \subseteq S}2^{e(T,S\setminus T)}=\sum_{T \subseteq S}2^{e(S)-e(T)-e(S\setminus T)}=2^{e(S)}\sum_{T \subseteq S}2^{-e(T)}2^{-e(S\setminus T)} \]

直接子集卷积。

数点双连通生成子图

给你一个无向图 \(G=(V,E)\)，求点双连通生成子图数量。

做法

我们考虑如何从点双连通分量得到连通图。

你可能会考虑耳分解之类的东西，但其实很简单。

我们依此扫每个点，每次将所有包含该点的点双连通分量合并就能得到连通图。

容易发现这是一一对应的。

假设我已经知道了对于每个点集 \(S\)，点双连通生成子图的个数 \(f_S\)，然后我们扫 \(i=1\dots n\)，每一次操作就是取出所有包含 \(i\) 的点集 \(S\)，去掉 \(i\) 之后进行 exp，然后再加回 \(i\) 放回 \(f\)。这被称作点双连通-连通变换。

我们考虑逆操作，取出所有包含 \(i\) 的点集 \(S\)，去掉 \(i\) 之后 ln，加上 \(i\) 再放回去。

单次 ln 是 \(O(n^2 2^n)\) 的，复杂度 \(\Theta(n^3 2^n)\)。

数边双连通生成子图

给你一个无向图 \(G=(V,E)\)，求边双连通生成子图数量。

做法1

我们可以这么刻画边双连通图。

• 点双大小不为 2 的连通图。

于是我们可以先求出点双连通生成子图数，然后去掉大小为 2 的，反过来再跑一遍正的，复杂度 \(\Theta(n^3 2^n)\)。

做法2

上面这个做法不够通用，我们尝试给出所谓边双连通-连通变换。

首先对于一张连通无向图，如果将所有边双缩起来，图会形成一棵树，树上的边是原图的割边。

考虑一个反过来的问题：假设给原图所有子集 \(S\subseteq U\) 均赋了权重 \(a_S\)，并定义一张连通子图的权值是其所有边双对应的 \(a\) 之积，并且我们还已经对所有 \(S\) 知道了 \(S\) 的边双连通生成子图数量是 \(b_S\)，如何求原图所有生成子图的权值和。

我们仿照之前思路，依次加点，每一次考虑所有编号 \(\le i\) 的 \(S\) 的生成子图的割边，再将所有经当前考虑的割边所连接的边双合并。

设考虑到 \(u\) 时的集合幂级数为 \(p_u\)，首先 \((p_0)_S=a_Sb_S\)。

那么考虑由 \(p_{u-1}\) 转移到 \(p_u\)，即加入所有两端编号最大值为 \(u\) 的割边。

先考虑加之前，此时对于点集 \(S\) 被分为 \(P_1,P_2,\dots,P_k\) 几块，假设 \(u \in P_1\)。

那么对于这样一个划分，贡献为

\[(p_{u-1})_{P_1}\sum_{i=2}^{k}(p_{u-1})_{P_i}e(\{u\},P_i) \]

例题 P4221 州区划分

\(n\) 座城市，每座城市有 \(w_i\) 人口，你要有序划分成若干州 \(\{V_1,\dots,V_k\}\)，每个州非空且导出子图不是欧拉图，定义一个州的满意度为

\[\left(\dfrac{\sum_{u \in V_i}w_u}{\sum_{j=1}^{i}\sum_{u \in v_j}w_u}\right)^p \]

定义一个划分方案的权值为所有州满意度的乘积。

求所有划分方案的权值和。

解法

首先欧拉图的限制是无关紧要的，直接判就可以了。

直接令 \(W_S=(\sum_{u \in S}w_u)^p\)，有转移

\[f_S=\dfrac{1}{W_S}\sum_{T \subseteq S}[T\text{ 非空且不是欧拉图}]W_Tf_{S\setminus T} \]

这里很烦的是带了一个 \(\dfrac{1}{W_S}\) 导致不能直接写成集合幂级数的形式。

回顾一下怎么求子集卷积的，每个 \(S\) 上维护了一个多项式，注意到子集卷积时每项次数只会变大。

于是我们枚举次数 \(0\dots n\)，每次跑一个 OR 卷积就可以了。