博弈论与状压

Weighted Tic-Tac-Toe

用二进制表示每一格的情况，然后必胜态和必败态需要相互转换。

Remove Pairs

直接状压，时间复杂度 $O(2^nn^2)$。

Exchange Game

$dp_{f,st}$ 表示某一方取，状态为 $st$ 时的赢家，由于涉及两方与牌堆，所以用三进制进行状压。放个核心代码：

int get (int nw,int p) {return nw / pw[p] % 3;}
int add (int nw,int p,int v) {return nw + (v - get (nw,p)) * pw[p];} 
bool dfs (bool f,int st)
{
    if (dp[f][st] != -1) return dp[f][st];//dp[f][st] 表示 f 取，状态为 st 时哪一方赢 
    for (int i = 0;i < N;++i)//出牌 
    {
        if (get (st,i) != f) continue;
        for (int j = 0;j < N;++j)//拿回 
        {
            if (get (st,j) != 2 || a[j] >= a[i]) continue;
            if (dfs (f ^ 1,add (add (st,i,2),j,f)) == f) return dp[f][st] = f; 
         }
         if (dfs (f ^ 1,add (st,i,2)) == f) return dp[f][st] = f;//不拿 
    }
    return dp[f][st] = f ^ 1;         
}