模拟赛考了这个 trick，感觉挺牛的。
直接放题。
题意
给定一个长度为 \(n\) 的序列 \(\{ a_i \}\)，令全集 \(U = \{ 1,2,3,\cdots,n \}\)，定义子集 \(S\) 的权值 \(g(S)=1+\oplus_{i\in S} a_i\)。
我们称集合 \(A=\{ T_1,T_2,\cdots,T_k\}\) 为 \(S\) 的划分，当且仅当：
- \(\forall 1\le i < j \le k，T_i \cap T_j = \emptyset\)。
- \(\cup_{i=1}^k T_i = S\)。
这里 \(T_i\) 允许为空。
下面用 \(A\sqsubseteq S\) 来表示 \(A\) 是 \(S\) 的划分。
我们定义 \(A\) 这个划分的权值为 \(\prod g(T_i)\)。现在给定一个整数 \(m\) 求 \(U\) 的所有大小为 \(m\) 的划分的权值的和。
注意： 此处划分的集合为有序集合，换句话说 \(\{ \{ 1,2 \} , \{3 \} \}\) 和 \(\{ \{3 \} , \{ 1,2 \} \}\) 是 \(\{ 1,2,3 \}\) 的两个不同的划分。
数据范围： \(1\le n\le 16\)，\(1\le m \le 10^9\)，\(1\le a_i \le 2^{30}\)。
题解
首先不难直接 DP 设 \(f_{i,S}\) 表示 \(S\) 的大小为 \(i\) 的划分的权值和，虽然 \(m\) 很大但是 \(n\) 很小因此很多集合都是空集，所以 \(i\) 这一维是 \(O(n)\) 的只需要在最后算答案的时候乘上一个组合数即可，复杂度 \(O(n3^n)\)。
也可以用子集卷积优化到 \(O(n^32^n)\)，但这跟正解关联不大。
考虑去掉 DP 的 \(n\)，因为题目要求了划分的大小，所以我们必须要记录一个 \(i\)。所以我们尝试通过配上一些容斥系数的手段来去掉这个划分大小的限制。
我们新定义一个子集 \(S\) 的权值 \(h(S)\)（\(S\ne \emptyset\)），令它满足：
其中 \(A\sqsubset S\) 表示 \(A\) 是 \(S\) 的真划分。
特殊的，\(g(\emptyset)=1\)。
真划分的定义：称无序集合 \(A=\{ T_1,T_2,\cdots,T_k\}\) 为 \(S\) 的真划分，当且仅当：
- \(\forall 1\le i \le k，T_i \ne \emptyset\)。
- \(\forall 1\le i < j \le k，T_i \cap T_j = \emptyset\)。
- \(\cup_{i=1}^k T_i = S\)。
换句话说 \(\sqsubset\) 和 \(\sqsubseteq\) 的区别仅在于他是无序的且不允许有空集。
先不管他有什么用，考虑怎么求出 \(h(S)\)，不难发现有如下递推式：
移项可得：
然后我们来求答案：
第一行是答案的定义，第二行是用 \(h\) 把 \(g\) 换掉，第四行是把 \(m^{|A|}\) 的每个 \(m\) 放到后面的 \(\prod\) 里。（当然对于那些 \(S_i=\emptyset\) 可能不能直接用第二行的表示，但这无伤大雅）
这里尽量用最简单的语言解释一下第三行。（当然会集合幂级数的话可以直接用集合幂级数理解）
设 \(H(A)=\prod_{T\in A} h(T)\)。
把 \(\prod_{i=1}^m \sum_{A\sqsubset S_i} \prod_{T\in A} h(T)\) 列出来，差不多长这样：
我们称这个形式为这组 \(\{ S_1,S_2,\cdots,S_m\}\) 对应的多项式。
其中 \(A_{i,j}\) 是 \(S_i\) 的某个真划分，当然对于那些 \(S_i=\emptyset\) 就用 \((1)\) 而不用 \((H(A_{i,1})+H(A_{i,2})+\cdots)\)，但是这并不影响下面的讨论，所以下面不特殊讨论这些 \(1\)。
考虑乘法分配律，从每个括号中选出一项乘起来，再把所有可能的组合加起来。
比如选出来的每个项的乘积是 \(\prod_{i=1}^m H(A_{i,id_i})\)，如果把 \(H\) 展开用 \(h\) 表示那么他就是一堆 \(h(T)\) 的乘积，设 \(\prod_{i=1}^m H(A_{i,id_i})=\prod_{i=1}^k h(T_k)\)。
虽然 \(k\) 的值并不是确定的，但不难证明不管我们取出的 \(\{ A_{i,id_i}\}\) 是什么样的，都一定满足：\(\{ T_1,T_2,\cdots T_k \}\sqsubset U\)。
但是这里我们并没有限制 \(k\) 的值要是多少，所以我们转而枚举符合条件的 \(A=\{ T_1,T_2,\cdots T_k \}\)，并计算他对答案的贡献。
那么答案可以写成：
其中 \(cnt(A)\) 表示对应的多项式中可以选出 \(A\) 这个真划分的 \(\{ S_1,S_2,\cdots,S_m\}\) 的数量。（显然一个多项式不可能有两种选择的方式选出同一个 \(A\)）
考虑怎么计算 \(cnt(A)\)，其实相当于就是要给 \(A\) 中的每个 \(T\) 分配到其中一个 \(S_i\) 中，每个 \(T\) 都可以分配到 \(m\) 个 \(S_i\) 中的任意一个，那么方案数就是 \(m^{|A|}\) 。
不妨验证一下这样分配是否符合题面中划分的定义：
首先显然满足 \(S_i\) 两两不交，且他们的并为 \(U\)。其次，当某个 \(S_i\) 没有被分配任何 \(T\) 时他就是空集（也就是说这样分配是可以分配出空集的）。最后，把 \(T_{i_1},T_{i_2},\cdots,T_{i_{c_1}}\) 分配给 \(T_i\) 并把 \(T_{j_1},T_{j_2},\cdots,T_{j_{c_2}}\) 分配给 \(T_j\) 和把 \(T_{i_1},T_{i_2},\cdots,T_{i_{c_1}}\) 分配给 \(T_j\) 并把 \(T_{j_1},T_{j_2},\cdots,T_{j_{c_2}}\) 分配给 \(T_i\) 会被我们算成两种不同的情况，因此这样分配出的 \(S_i\) 确实是有序的。
这样我们就把大小为 \(m\) 这个限制去掉了，\(ans=\sum_{A \sqsubset U} \prod_{T\in A} m\cdot h(T)\) 这个式子显然可以直接用状压 DP 计算，直接设 \(f_S\) 表示 \(S\) 的答案则：
边界为 \(f_{\emptyset}=1\)，复杂度 \(O(3^n)\)。
code
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
using namespace std;
const int N=(1<<16)+5,mod=1e9+7;inline int read(){int w=1,s=0;char c=getchar();for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());return w*s;
}
int n,m,a[20],f[N],g[N],h[N];
int lowbit(int x){return x&(-x);}
void add(int &x,int y){(x+=y)%=mod;}
signed main(){freopen("partition.in","r",stdin);freopen("partition.out","w",stdout);n=read(),m=read();for(int i=0;i<n;i++) a[i]=read();for(int S=0;S<(1<<n);S++){g[S]=0;for(int i=0;i<n;i++) if(S>>i&1) g[S]^=a[i];add(g[S],1);if(S){for(int T=(S-1)&S;T;T=(T-1)&S) if(T&lowbit(S)) add(h[S],1ll*h[T]*g[S^T]%mod);h[S]=(g[S]-h[S]+mod)%mod;}}f[0]=1;for(int S=1;S<(1<<n);S++){for(int T=S;T;T=(T-1)&S) if(T&lowbit(S)) add(f[S],1ll*m*h[T]%mod*f[S^T]%mod);}printf("%d\n",f[(1<<n)-1]);return 0;
}
暂未发现更多例题，欢迎分享。