CF768E Game of Stones(状压DP+博弈论)

题目大意：

给出n堆石子，A和B来取，一次可以取一堆中的若干个，本身是nim游戏的框架，不过多加了这样的一个限制：

如果其中一堆之前已经被取过k个了，那么就不能再取k个

题解：

还是把每一堆石子看成一个子游戏，最后异或起来即可

然后就是求SG函数（dp）

利用状压，把每一个数（1到60）有没有取的状态压到一个60位的2进制里

如果每个状态都计算，显然会超时

但是实际上并没有特别多的状态可以取，实际状态数大概只有60这个数的有限制的整数拆分方案个数

这样就完成状态的压缩

dp[i][s]表示已经取了s这个状态代表的数，现在还有i个石子的SG值

转移就是按照SG函数的定义，往能够达到的局面转移，过程可以利用记忆化搜索

为了节省空间，这里利用map来实现整个过程

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
map<pair<int, long long>, int> dp;
map<pair<int, long long>, bool> visit;
int dfs(int x, long long S){
    S = S&((1LL<<x)-1);
    if(x == 0) return 0;
    if(visit[{x, S}]) return dp[{x, S}];
    vector<bool> f(63, 0);
    for(int i = x; i >= 1; i--){
        long long Si = 1<<(i-1);
        if(S&Si) continue;
        f[dfs(x-i, S|Si)] = 1;
    }
    for(int i = 0; i < 63; i++) if(!f[i]){
        visit[{x, S}] = true;
        return dp[{x, S}] = i;
    }
}

int main()
{
    int n, x;
    cin>>n;
    for(int i = 60; i >= 0; i--) dfs(i, 0);
    int SG = 0;
    for(int i = 0; i < n; i++) scanf("%d", &x), SG ^= dp[{x, 0}];
    if(SG) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

}