2020ccpc Weihai J - Steins; Game (SG function, linear basis)

The question ：n Rubble , Each pile of stones has two colors black and white , When taking black stones, you must take the least amount （ At least one ）, There is no limit to white, you can take it at will （ At least one ）. The backhand can dye all the stones before the game starts , Ask the number of coloring schemes that the backhand can win .

Answer key ： First, you can divide black and white into two games , The XOR sum of two games is 0 That is, the backhand wins .

White game ： amount to nim game

Black game ： adopt sg You can find

SG value = Minimum number of stones − ( ( Minimum number of heaps + [ The number of all stones is the same ] ) % 2 )

Can find sg The value is only related to the smallest heap , Then we can enumerate the smallest heap . Use one pre Maintain XOR prefix and ,suf Maintain XOR suffixes and , Maintain a linear basis from back to front . Because the heap we enumerated is the smallest heap , Therefore, the pile with less stones than the current enumeration must be white , We want the final total XOR value to be 0, Then it depends on whether the linear basis can satisfy XOR and as 0 Number of numbers , Scheme i.e 2 Of (s - tot) Power . Finally, multiply by a combined number . The detailed code can be seen .

sg Function table code ：

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int sg[N];

int SG(priority_queue<int, vector<int>, greater<int> > q) {
    
	bool vis[N] = {
     false };
	if (q.empty()) return 0;
	int t = q.top();
	q.pop();
	vis[SG(q)] = true;
	for (int i = 1; i < t; i++) {
    
		auto tmp = q;
		tmp.push(t - i);
		vis[SG(tmp)] = true;
	}
	for (int i = 0; ; i++)
		if (!vis[i]) return i;
}

int main() {
    
	priority_queue<int, vector<int>, greater<int> > q;
	for (int i = 0; i <= 5; i++) {
    
		for (int j = i; j <= 5; j++) {
    
			for (int k = j; k <= 5; k++) {
    
				for (int l = k; l <= 5; l++) {
    
					for (int r = l; r <= 5; r++) {
    
						while (!q.empty()) q.pop();
						if (i) q.push(i), cout << i << " ";
						if (j) q.push(j), cout << j << " ";
						if (k) q.push(k), cout << k << " ";
						if (l) q.push(l), cout << l << " ";
						if (r) q.push(r), cout << r << " ";
						cout << " : " << SG(q) << endl;
					}
				}
			}
		}
	}
	return 0;
}

Title code ：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int f[N], inv[N];
int a[N], pre[N], suf[N];
int same[N], num[N];
map<int, int> t;
struct LB {
    
	const static int N = 64;
	ll a[N + 1], tot;
	LB() {
     memset(a, 0, sizeof(a)), tot = 0; }
	bool insert(ll x) {
    
		for (int i = N; i >= 0; i--) {
    
			if (x & (1ll << i)) {
    
				if (a[i]) x ^= a[i];
				else {
    
					a[i] = x;
					tot++;
					break;
				}
			}
		}
		return x > 0;
	}
	bool count(ll x) {
    
		for (int i = N; i >= 0; i--)
			if (x & (1ll << i)) x ^= a[i];
		return x == 0;
	}
}LB;

int qpow(int a, int b) {
    
	int res = 1;
	while (b) {
    
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(int n) {
    
	f[0] = inv[0] = 1;
	for (int i = 1; i <= n; i++)
		f[i] = f[i - 1] * i % mod;
	inv[n] = qpow(f[n], mod - 2);
	for (int i = n - 1; i >= 1; i--)
		inv[i] = inv[i + 1] * (i + 1) % mod;
}

int C(int a, int b) {
    
	if (a < b) return 0;
	return f[a] * inv[b] % mod * inv[a - b] % mod;
}

signed main() {
    
	init(N - 1);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
    
		cin >> a[i];
		t[a[i]]++;
		ans ^= a[i];
	}
	ans = (ans == 0 ? 1 : 0);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		pre[i] = pre[i - 1] ^ a[i];
	for (int i = n; i >= 1; i--)
		suf[i] = suf[i + 1] ^ a[i];
	for (int i = n; i >= 1; i--) {
    
		same[i] = (a[i] == a[i + 1] ? same[i + 1] + 1 : 1);
		num[i] = t[a[i]];
	}
	int head = n + 1;
	for (int i = n; i >= 1; i--) {
    
		int sum = 0;// Record the plan 
		int x = pre[i - 1];// Prefix exclusive or and 
		int y = a[i] - ((same[i] + 1) & 1);
		// Currently selected same[i] The number of pieces is a[i] The stone pile is dyed black ( All stone heaps have the same number of stones )
		int z = suf[i + same[i]];// Suffix XOR and 
		if ((x ^ y ^ z) == 0) sum = (sum + 1) % mod;// If XOR and is 0, Method number plus one 
		y = a[i] - (same[i] & 1);// ditto y, But the number of stones in all stone piles is different 
		int need = x ^ y;// Satisfy XOR and do 0 Number of numbers 

		if (LB.count(need)) sum = (sum + qpow(2, n - head + 1 - LB.tot)) % mod;
		// If need It can be expressed by linear basis , The scheme that the linear basis can express this number is 2^(s - tot)
		//s Is the number of linear basis insertions ,tot Is the number in the linear base 

		if ((need ^ suf[i + same[i]]) == 0) sum = (sum - 1 + mod) % mod;
		// If the suffix all numbers are XOR and equal need Then the number of schemes should be reduced by one 

		if (same[i - 1] == 1) {
    
			// If it is currently a[i] The last stone pile of the quantity , Set all values to a[i] Insert the number of into the linear base 
			for (int j = 1; j <= same[i]; j++) LB.insert(a[i]);
			head = i;
		}
		ans = (ans + sum * C(num[i], same[i]) % mod) % mod;
		// Finally, take the bus at num[i] Middle selection same[i] Number of heap methods 
	}
	cout << ans << endl;
	return 0;
}