$闹腾$Nim游戏题解

关于本题

我们可以转移一个$f[i][j][k]$表示从前$i$堆中取，丢掉了$j$堆在$mod$$s$时，$xor$值为$k$的方案数

f[i][j][k] = f[i - 1][[j - 1][k ^ $a_i$] + f[i - 1][j][k];

有一个很巧妙的想法是：因为对于任意一个正整数$A$, 它和比它自己小的数字异或起来的结果不会超过$2A$,由此可以得出：$a_i$和比$a_i$小的数字的异或和不会超过2$a_i$,此我们可以直接对石子排序，这样的时间复杂度就可以减少到$O(nd)$。 最后有个小细节要注意一下：当$s$可以被$n$整除时，结果要减去1

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;
const int N = 2e6 + 10,M = 5 * 1e5 + 10,mod = 1e9 + 7;
int n,k;
int a[M];
int f[10][N];//f[i][j][k]从前i堆中取，丢掉了j堆，xor值为k的方案数
int flags[N],tmp = 1;

int maxn = 0;

signed main()
{
	//freopen("4.in","r",stdin);
	cin >> n >> k;
	for (int i = 1;i <= n;i ++)
	{
		cin >> a[i];maxn ^= a[i];
	}
	
	sort(a + 1,a + n + 1);
	
	f[0][0] = 1;
	
	for (int i = 1;i <= n;i ++)
	{
		for (;tmp <= a[i];tmp <<= 1);
		for (int j = 0;j < tmp;j ++) flags[j] = (f[k - 1][j ^ a[i]] + f[0][j]) % mod;
		
		//DP : bag
		for (int j = k - 1;j > 0;j --)
		{
			for (int h = 0;h < tmp;h ++)
			{
				f[j][h] = (f[j - 1][h ^ a[i]] + f[j][h]) % mod;
			}
		}
		
		for (int j = 0;j < tmp;j ++) f[0][j] = flags[j];
	}
	
	if (n % k == 0) 	
	{
	    cout << (f[0][maxn] - 1 + mod) % mod << endl;
	    return 0;
	}
	
	cout << (f[0][maxn] + mod) % mod << endl;
	return 0;
}