[IOI Camp Judge 48]Kokokko

IOI Camp Judge是暫時性的，因此我在這裡做了題目備份，請參考~

首先，我們可以證明每個巧克力是獨立的遊戲

我們先修改一下規則，同一個位置可以疊任意各數的巧克力，壓克力視為$0$個巧克力
那麼對於位置在$(x,y)$的巧克力，玩家可以選一個座標$(x_{0},y_{0})$ ($0\leq x_{0}<x,0\leq y_{0}<y$)，把$(x_{0},y_{0})$、$(x_{0},y)$、$(x,y_{0})$疊上一個巧克力，$(x,y)$拿掉一個巧克力，這樣$(x,y)$就轉換成$(x_{0},y_{0})$、$(x_{0},y)$、$(x,y_{0})$這三個子遊戲了！
因此$SG(x,y)=mex\{SG(x_{0},y_{0})\bigoplus SG(x_{0},y)\bigoplus SG(x,y_{0}),0\leq x_{0}<x,0\leq y_{0}<y\}$ ($SG(x,y)$為在$(x,y)$這個位置上的巧克力的$SG$函數值，$\bigoplus$是XOR的符號)
如果$x$座標或$y$座標是$0$，因為是無效的子遊戲，因此$SG$函數值是$0$

這個修改過規則的遊戲，$SG$函數和原題是一樣的
為甚麼呢？
因為每個巧克力的$SG$函數值$XOR$起來，同一個位置的巧克力就兩兩消除變成等價了

這$20*20$個位置的$SG$函數值可以$O(20^{4})$預處理出來 (記憶化搜索或迴圈遞推皆可)
因此，給定任意一個盤面，我們可以把每個位置的巧克力的$SG$函數值$XOR$起來，就是整個盤面的$SG$函數值了

但，這題等價要你選出$K$個不同的位置，使得它們的$SG$函數值$XOR$起來$=0$

我們可以把這$M*N$個數字 ($SG$函數值) 變成一個序列$\{S_{i}\}$，對於每個元素，可以選或不選，最後看看有沒有恰好選$K$個且$XOR$起來$=0$的方法

我們可以構造一個$DP$，$DP[i][j][k]$代表現在考慮了$S_{1},S_{2},...,S_{i}$，能不能選出$j$個數字使得它們$XOR$起來$=k$，用$true$或$false$表示

初始條件：$DP[0][0][0]=true$，其他$DP[0][j][k]=false$
轉移方式就是對於每個值為$true$的$DP[i][j][k]$，將$DP[i+1][j][k]$和$DP[i+1][j+1][k\bigoplus S_{i+1}]$都設成$true$

最後看看$DP[N*M][K][0]$是不是$true$，是的話回溯找出一組選法 (因此需要在$DP$的時候將中間結果記錄下來)

時間複雜度：$O(20^{4}+T*(NM)^{2}*512)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
int SG[21][21];
int GetSG(const int row,const int col)
{
    int &ans=SG[row][col];
    if(ans!=-1)return ans;
    vector<int>s;
    for(int i=0;i<row;i++)for(int j=0;j<col;j++)
    {
        s.push_back(GetSG(i,j)^GetSG(i,col)^GetSG(row,j));
    }
    sort(s.begin(),s.end()),s.resize(unique(s.begin(),s.end())-s.begin());
    for(ans=0;ans<(int)s.size()&&s[ans]==ans;ans++);
    return ans;
}
int N,M;
multiset<int>ANS;
bool Solve(int K)
{
    vector<int>s;
    s.push_back(-1);
    for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)s.push_back(GetSG(i,j));
    static bool dp[401][401][512],used[401][401][512];
    for(int i=0;i<=400;i++)for(int j=0;j<512;j++)dp[0][i][j]=false;
    dp[0][0][0]=true,used[0][0][0]=false;
    for(int idx=1;idx<(int)s.size();idx++)
    {
        for(int i=0;i<=400;i++)for(int j=0;j<512;j++)dp[idx][i][j]=false;
        for(int i=0;i<=400;i++)for(int j=0;j<512;j++)if(dp[idx-1][i][j])
        {
            dp[idx][i][j]=true,used[idx][i][j]=false;
            dp[idx][i+1][j^s[idx]]=true,used[idx][i+1][j^s[idx]]=true;
        }
    }
    assert(N*M==(int)s.size()-1);
    if(!dp[N*M][K][0])return false;
    ANS.clear();
    for(int cur=0,i=N*M;i>=0;i--)
    {
        if(used[i][K][cur])
        {
            ANS.insert(s[i]);
            cur^=s[i];
            K--;
        }
    }
    return true;
}
int K;
int main()
{
//    freopen("in.txt","r",stdin);
    for(int i=0;i<=20;i++)for(int j=0;j<=20;j++)SG[i][j]=0;
    for(int i=1;i<=20;i++)for(int j=1;j<=20;j++)SG[i][j]=-1;
//    for(int i=1;i<=20;i++)
//    {
//        for(int j=1;j<=20;j++)printf("%d ",GetSG(i,j));
//        puts("");
//    }
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d%d",&N,&M,&K);
        if(Solve(K))
        {
            puts("^v^;;");
            assert((int)ANS.size()==K);
            int check=0;
            for(int i=1;i<=N;i++)
            {
                for(int j=1;j<=M;j++)
                {
                    const auto it=ANS.find(GetSG(i,j));
                    if(it!=ANS.end()){ANS.erase(it);putchar('C');check^=GetSG(i,j);}
                    else putchar('A');
                }
                puts("");
            }
            assert(ANS.empty());
            assert(check==0);
        }
        else puts("ko_ko_ko");
    }
    return 0;
}