模擬賽考了這個 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;
}

我們在最后再回頭看新定義的這個 \(h(S)\) 的用途，它相當于是讓原先每一個已經劃分出來的子集 \(S_i\) 可以繼續劃分下去，從而去掉 \(m\) 這個限制。但是新問題的每個子集的貢獻顯然不是原先的 \(g(S)\) 了因此我們需要重新給每個子集計算貢獻 \(h(S)\)（或者說給每個子集配了容斥系數）。

暫未發現更多例題，歡迎分享。