UESTC 1661 Playing With Stones 博弈打表

You and your friend are playing a game in which you and your friend take turns removing stones from piles. Initially there are  N N piles with  a1,a2,a3,…,aN a1,a2,a3,…,aN number of stones. On each turn, a player must remove at least one stone from one pile but no more than half of the number of stones in that pile. The player who cannot make any moves is considered lost. For example, if there are three piles with  5 5,  1 1 and  2 2stones, then the player can take  1 1 or  2 2 stones from first pile, no stone from second pile, and only  1 1 stone from third pile. Note that the player cannot take any stones from the second pile as  1 1 is more than half of  1 1 (the size of that pile). Assume that you and your friend play optimally and you play first, determine whether you have a winning move. You are said to have a winning move if after making that move, you can eventually win no matter what your friend does.

The first line of input contains an integer  T T  (T≤100) (T≤100) denoting the number of testcases. Each testcase begins with an integer  N N  (1≤N≤100) (1≤N≤100) the number of piles. The next line contains  N N integers  a1,a2,a3,…,aN a1,a2,a3,…,aN  (1≤ai≤2∗1018) (1≤ai≤2∗1018) the number of stones in each pile.

For each testcase, print “ YES YES” (without quote) if you have a winning move, or “ NO NO” (without quote) if you don‟t have a winning move.

4
2
4 4
3
1 2 3
3
2 4 6
3
1 2 1

NO
YES
NO
YES

数据这么大，一看就要打表找规律。

事实上，sg函数确实有规律。

规律较复杂，不过推个公式还是可以的。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=105,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f; 
const ld pi=acos(-1.0L);
ll a[maxn],b[maxn];
int m;ll getsg(ll p) {ll n=p;int k,i;for (i=1;i<=m;i++) {if (b[i+1]>n) break; }k=i;if (b[i+1]==n+1) return 0;while (((n-b[k])/2)%2!=0) {n/=2;k--;}return (b[k]/4)+(n-b[k])/4;
}int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);int cas;ll i;map<ll,int> sg;scanf("%d",&cas);for (i=1;i<=2e18;i=i*2+1) {sg[i]=1;}m=0;for (i=2;i<=2e18;i*=2) {b[++m]=i;}b[++m]=i;while (cas--) {int n,j;scanf("%d",&n);ll sum=0;for (i=1;i<=n;i++) {scanf("%lld",&a[i]);if (a[i]%2==0) sum=sum^(a[i]/2); else {//		cout << a[i] << ' ' << getsg(a[i]);sum=sum^(getsg(a[i]));}}if (sum!=0) cout << "YES" << endl; else cout << "NO" << endl;}return 0;
}