「ZJOI2016」小星星

题目链接：https://loj.ac/p/2091

---

前置知识：\(FWT\)。

（建议看这个博客：https://www.cnblogs.com/chasedeath/p/12785842.html）

一眼状压，考虑写出最暴力的 dp。

设 \(f(u,a,sta)\) 表示以 \(u\) 为根的子树且 \(u\) 的编号为 \(a\) 且用掉的编号集合为 \(sta\)。

那么对于每个点枚举自己的儿子 \(v\)， 并且枚举 \(a,b\) 分别表示 \(u,v\) 的编号，再枚举子集进行统计即可。

设 \(\oplus\) 表示异或，且下文所有写到的 \(b\) 仅指满足原饰品中与 \(a\) 相连的编号。即下文提到的 \(b\) 皆满足题给的合法条件。

那么就有：

\[f(u,a,S)=\sum_{v}\sum_{b}\sum_{T\subseteq S}f(v,b,T)\times f(u,a,T\oplus S) \]

考虑使用前缀和优化，处理出对于每个 \(a\) 合法的 \(f(v,b,T)\) 之和。

那么设 \(g(v,T)_a=\sum_bf(v,b,T)\)。

就有：

\[f(u,a,S)=\sum_{v}\sum_{T\subseteq S} g(v,T)_a\times f(u,a,T\oplus S) \]

直接根据这个式子计算答案时间复杂度是 \(O(n^2\times3^n)\) 的。

而注意到这个式子的形式跟下面这个式子的形式非常相似：

\[f_S=\sum_{R\oplus T=S} g_R\times h_T \]

那么我们将原式变换一下：

\[f(u,a,S)=\sum_v\sum_{T\oplus R=S,T\cap R=\varnothing} g(v,T)_a\times f(u,a,R) \]

由于 \(T\cap R=\varnothing\) 这个条件比较苛刻，直接 \(FWT\) 的话单次需要 \(O(n^2\times2^n)\)。总和就要 \(O(n^4\times2^n)\)了。

考虑去掉这个条件。

设 \(pc(i)\) 表示将 \(i\) 用二进制表示后有几个 \(1\)。

对于所有值不为 \(0\) 的 \(f(u,a,R_1),f(u,a,R_2)\dots f(u,a,R_k)\)，一定有 \(pc(R_1)=pc(R_2)=\dots pc(R_k)\)。

因为每个点恰有一个编号，所以对于 \(pc(R)\not = siz_u\) （\(siz_u\) 表示 \(u\) 的子树大小），\(f(u,a,R)=0\)。

（同时 \(siz_u\) 也可以表示加入儿子 \(v\) 之前加入的总点数）。

再考虑一下异或的性质：若有 \(pc(S)+pc(T)=pc(S\oplus T)\) ，则有 \(S\cap T=\varnothing\)，否则 \(S\cap R\not=\varnothing\)。

所以原式子可以直接变成：

\[f(u,a,S)=\sum_v\sum_{T\oplus R=S} g(v,T)_a\times f(u,a,R) \]

之后对于所有 \(S\) 满足 \(pc(S)\not= siz_u+siz_v\)，我们手动赋值使 \(f(u,a,S)=0\) 即可。

那么对于后面这个式子：

\[\sum_{T\oplus R=S} g(v,T)_a\times f(u,a,R) \]

直接用 \(FWT\) 处理即可，单次复杂度是 \(O(n\times 2^n)\)。总时间复杂度就是 \(O(n^3\times 2^n)\)。

此外，由于空间限制不能直接开空间为 \(O(n^2\times 2^n)\) 的数组。但是考虑除了 \(pc(S)=siz_u\) 的情况下其余 \(f\) 值皆为 \(0\)。而满足 \(pc(S)=siz_u\) 的 \(S\) 最多只有 \(2.5e4\) 个，所以离散化一下即可。

但是常数极大，可以通过 LOJ 但是不能通过 luogu。

代码如下：

#include
#define ll long long
using namespace std;
const int MAXN = 18;
bool Sunny;
ll f[MAXN][MAXN][30005],res[(1<<17)],C[(1<<17)],B[(1<<17)];
int A[MAXN][30005],S[MAXN],siz[MAXN];
int id[(1<<17)+5];
int n,m;
bool link[MAXN][MAXN],e[MAXN][MAXN];
bool Small;
inline void FWT()
{
	for(int l=1;l<(1<