題目鏈接：D - Xor Sum 5

題目大意：給定一個長度為 \(N(1\le N\le 1000)\) 的數組 \(A(0\le A_i\le 1000)\)，以及一個正整數 \(K(1\le K\le 10^{12})\)?，F在要在這 \(N\) 個數字里挑一個 \(A_i\) 出來，并重復 \(K\) 次這樣的操作，對應的得分就是挑出來的 \(A_i\) 之和。一共有 \(N^K\) 種挑選方案，求所有挑選方案對應得分的異或和。

簡化問題

將問題轉化成生成函數來表示，那就是令 \(P(x)=(x^{A_1}+x^{A_2}+...+x^{A_N})^K\)，并求所有系數為奇數對應項的指數之和。那么考慮模 \(2\) 意義下的多項式運算，就是求滿足 \([x^S](x^{A_1}+x^{A_2}+...+x^{A_N})^K\) 的值為 \(1\) 對應的所有 \(S\) 的異或和。

接著考慮模 \(2\) 意義下的一個經典式子：

反復套用對應式子，我們得到：

其實對于這個式子，我們也可以用 \(\texttt{Lucas}\) 定理的推論來證明：

• 經典推論：\((x+y)^P\equiv x^P+y^P\pmod P\)，其中 \(P\) 為質數（考慮 \(\binom{P}{i}\) 不為 \(P\) 的倍數當且僅當 \(i=0\) 或 \(P\)）
• 對 \(P=2\)，得出 \((x+y)^2\equiv x^2+y^2 \pmod 2\)
• 反復套用該式，得出 \((\sum_{i=1}^n x_i)^2\equiv (\sum_{i=1}^{n-1} x_i)^2+x_n^2\equiv ...\equiv \sum_{i=1}^n x_i^2\)

回到原問題，考慮 \(K\) 的二進制表達 \(K=\sum_{i=1}^{M}2^{k_i}\)，那么就有：

記第 \(i\) 次選擇的數字下標為 \(X_i\)，于是問題就由求 \(\sum_{i=1}^K A_{X_i}\) 的異或和變成了求 \(\sum_{m=1}^M A_{X_m}\times 2^{k_m}=S\) 的異或和。

組合計數

我們可以將這一問題轉化為一道組合計數問題：對每個結果 \(S\)，確定 \(\sum_{m=1}^M A_{X_m}\times 2^{k_m}=S\) 的方案數。由于我們最后求的是異或和，那么我們只需要統計方案數為奇數的答案即可，進一步地，我們考慮求和結果在二進制的某一位上為 \(1\) 的方案數。

考慮動態維護所有滿足方案數為奇數的 \(S\) 組成的集合。設當前考慮的是二進制第 \(i\) 位上的答案，顯然更低位的信息我們是不需要的，所以我們動態維護所有的 \(\lfloor\frac{S}{2^i}\rfloor\)。又因為當 \(k_m>i\) 時，\(A_{X_m}\times 2^{k_m}\) 對答案的第 \(i\) 位不產生貢獻，所以我們可以等到 \(i=k_m\) 時再考慮對應 \(A_{X_m}\times 2^{k_m}\) 的選擇。

于是在過程中，當我們考慮到第 \(i\) 位時，集合中的元素個數。可以估算得出，集合中元素的最大值對應上界為：

所以在這個過程中，集合的大小始終是不超過 \(2\max (A)\) 的。于是我們直接暴力維護集合即可在 \(O(N^2\log K)\) 的復雜度內解決問題，每次統計答案時只需要統計集合內有多少個奇數即可。使用 \(\texttt{bitset}\) 可以進行進一步的常數優化。

要注意的是，由于在考慮前面幾位的答案時，對于 \(k_m>i\) 對應的 \(A_{X_m}\times 2^{k_m}\) 選擇方案數還沒有被統計進來，所以實際上這時對應的方案數還要乘上一個 \(N\) 的若干次方 \(N^{阿巴阿巴}\)。因此當還存在 \(k_m>i\) 時，我們還需要根據 \(N\) 的奇偶性來判斷當前位置是否可能有值。此外當 \(i=k_M\) 時我們也可以直接計算最終答案，具體實現見代碼。

#include<bits/stdc++.h>
using namespace std;
#define N 2048
int n;
bitset<N>a,s,t;
long long k,ans;
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a.flip(x);
	}
	s[0]=1;
	for(int i=0;i<=40;i++){
		for(int j=0;j<N;j++)if(s[j])
			s.flip(j/2),s.flip(j);
		if(k>>i&1){
			t.reset();
			k^=(1ll<<i);
			for(int x=0;x<N/2;x++)if(a[x])
				t=t^(s<<x);
			s=t;
		}
		if(k==0){
			long long res=0;
			for(int j=0;j<N;j++)if(s[j])res^=j;
			ans+=res<<i;
			return printf("%lld\n",ans),0;
		}
		if(n&1){
			long long o=0;
			for(int j=1;j<N;j+=2)if(s[j])o^=1;
			ans+=o<<i;
		}
	}
}