Solution
注意到 \(n\le21\)，优先考虑状压。
记全集为 \(U\)，\(f_S\) 为点集 \(S\) 的所有合法的划分方案的满意度之和，\(\operatorname{Sum}(S)\) 为点集 \(S\) 的人口和，即 \(\sum_{x\in S}w_x\)，\(g_S\) 为点集 \(S\) 是否合法（合法为 \(1\)，否则为 \(0\)）。根据题意可写出如下转移方程：
\[f_S = \sum_{L\subseteq U}\sum_{R\subseteq U}[L\cup R=S][L\cap R=\varnothing]f[L]g[R]\times\left(\frac{\operatorname{Sum}(R)}{\operatorname{Sum}(S)}\right)^p\\
\]
把最后的一项拆开，记 \(h_S=g_S\times\operatorname{Sum}(S)^p\)。
\[f_S=\frac{1}{\operatorname{Sum(S)}^p}\sum_{L\subseteq U}\sum_{R\subseteq U}[L\cup R=S][L\cap R=\varnothing]f_Lh_R\\
\]
\[f_{S,c}=\frac{1}{\operatorname{Sum(S)}^p}\sum_{L\cup R=S}f_{L,a}h_{R,c-a}\\
\]
\[f_{S,c}=\frac{1}{\operatorname{Sum(S)}^p}\sum_{L\operatorname{or} R=S}f_L h_R\\
\]
和这个 FMT 一毛一样了：
\[c_i = \sum_{j\operatorname{or}k=i}a_jb_k\\
\]