QOJ # 9567. Toe-Tac-Tics 并不是题解而是超现实数入门（3）
MatrixGroup
·
·
题解
题目链接
南京站过后大家都会超现实数了啊？？
前置知识：[ABC229H] Advance or Eat 并不是题解而是超现实数入门（涉及超现实数的定义和生日有限的超现实数值的确定），[いろはちゃんコンテスト Day4 J]もう、諦めない 并不是题解而是超现实数入门（2）（涉及了基本的伪数知识）。
总之一句话总结就是超现实数/伪数刻画了一个非对称博弈，它的正负性可以确定谁必胜，每个生日有限的超现实数可以对应 \Z[1/2] 中的一个有理数，数/伪数的加法就是游戏的 disjunctive sum。
看起来这个题里面大概是双方都不想走的，因为走了更容易连成线输掉。但是考虑这么一个情况：
.x.
xox
oxx
这时谁走了左上角谁就赢了，因为剩下的那个格子走不了。这个游戏的值为 (\{0\},\{0\})=\ast。
考虑猜测所有游戏的值都为 a+\ast_b，其中 a 是超现实数，b 是序数（\ast_b 表示 Nimber b，即以上链接第二篇中的 h(b)）。本文稍微详细地讲解 a+\ast_b 相关计算。（其实打表可得要么是 a 要么是 a+\ast）
定理. 若 b\neq 0 为序数，对于数 x，若 x<0，则 x<\ast_b；若 x=0，则 x||\ast_b；若 x>0，则 x>\ast_b。
证明. 可以归纳计算出 L(\ast_b)=R(0),R(\ast_b)=L(0)，即证。
定理. 若 a,b 为序数，\ast_a\le \ast_b 当且仅当 a=b。
证明. 充分性显然。考虑必要性。若 a<b，则 \ast_a 在 \ast_b 的右集中，故 \ast_a\nleq \ast_b。若 a>b，则 \ast_b 在 \ast_a 的左集中，故 \ast_a\nleq \ast_b。故 a=b。
推论. 若 a,b 为序数，若 a=b 则有 \ast_a=\ast_b，否则 \ast_a||\ast_b。
定理. （Sprague–Grundy 定理）设 S 为序数的集合，则 (\{\ast_b|b\in S\},\{\ast_b|b\in S\})=\ast_{\operatorname{mex} S}。
证明.
$(\{\ast_b|b\in S\},\{\ast_b|b\in S\})\ge \ast_{\operatorname{mex} S}$. 只需证明 $\forall b\in S,\ast_b\nleq\ast_{\operatorname{mex} S}$，且 $\forall c<\operatorname{mex}S,(\{\ast_b|b\in S\},\{\ast_b|b\in S\})\nleq \ast_c$。因为 $b\in S$，故 $b\neq \operatorname{mex}(S)$，故前者显然。而 $\ast_c$ 属于该数的左集，故后者也显然。
**推论.** 若 $a,b\neq 0$ 为序数，则 $\ast _a+\ast_b=\ast_{a\oplus b}$。
**推论.** 任意对称博弈等于某个 $\ast_b$。
**定理.** 若 $b\neq 0$ 为序数，$a+\ast_b=(\{a+\ast_{c}|c<b\},\{a+\ast_{c}|c<b\})$。（注：$b$ 为非负整数的情况可以使用**平移定理**证明。）
**证明.** 对 $a$ 归纳。
根据定义，设 $a$ 为 $(A_L,A_R)$，则 $a+\ast_b=(\{a+\ast_{c}|c<b\}\cup\{a_L+\ast_b|a_L\in A_L\},\{a+\ast_{c}|c<b\}\cup\{a_R+\ast_b|a_R\in A_R\})$。根据推论 17.1，只需证明 $\forall a_L\in A_L\exists c<b$ 有 $a+\ast_c\ge a_L+\ast_b$，且 $\forall a_R\in A_R\exists c<b$ 有 $a+\ast_c\le a_R+\ast_b$。不妨取 $c=0$。
$a\ge a_L+\ast_b$. 只需验证 $\nexists a_R\in A_R,a_R\le a_L+\ast_b$ 且 $\nexists c<b,a\le a_L+\ast_c$（因为归纳假设，$a_L+\ast_b$ 的左集只需要考虑 $a_L+\ast_c$）。前者由 $a_R\ge a_L\nleq a_L+\ast_b$ 保证，后者若 $c=0$ 则有 $a\nleq a_L$，若 $c\neq0$ 有 $a\geq a_L\nleq a_L+\ast_c$。
$a\le a_R+\ast_b$. 只需验证 $\nexists a_L\in _AL,a_L\ge a_R+\ast _b$ 且 $\nexists c<b,a\ge a_R+\ast_c$（因为归纳假设，$a_R+\ast_b$ 的右集只需要考虑 $a_R+\ast _c$）。前者由 $a_L\le a_R\ngeq a_R+\ast_b$ 保证，后者若 $c=0$ 则有 $a\ngeq a_R$，若 $c\neq 0$ 有 $a\le a_R\ngeq a_R+\ast_c$。
**定理.** 对于任何 $a$ 为 $(A_L,A_R)$，对于任何 $a_L\in A_L$ 和序数 $b$，有 $a> a_L+\ast_b$。对于任何 $a_R\in A_R$ 和序数 $b$，有 $a<a_R+\ast _b$。
**证明.**
在上个定理的证明过程中证明过了 $a\ge a_L+\ast _b$，而若 $b=0$ 有 $a\nleq a_L$，否则有 $a\ge a_L\nleq a_L+\ast _b$，故 $a>a_L+\ast_b$。
在上个定理的证明过程中证明过了 $a\le a_R+\ast _b$，而若 $b=0$ 有 $a\ngeq a_R$，否则有 $a\le a_R\ngeq a_R+\ast _b$，故 $a<a_R+\ast_b$。
**定理.** 若 $a,b$ 为数，$c,d$ 为序数，则：若 $a<b$，有 $a+\ast_c<b+\ast_d$。若 $a>b$，有 $a+\ast_c>b+\ast_d$。若 $a=b$ 且 $c=d$，有 $a+\ast_c=b+\ast_d$。若 $a=b$ 且 $c\neq d$，有 $a+\ast_c||b+\ast_d$。
**证明.**
若 $a<b$，有 $a+\ast_c< (\{a\},\{b\})<b+\ast_d$。
若 $a>b$，有 $a+\ast_c>(\{b\},\{a\})>b+\ast_d$。
若 $a=b$ 且 $c=d$，显然有 $a+\ast_c=b+\ast_d$。
若 $a=b$ 且 $c\neq d$，因为有 $\ast_c||\ast_d$，显然有 $a+\ast_c||b+\ast_d$。
**定理.** 设 $g$ 为 $(G_L,G_R)$，其中每个 $g_L\in G_L$ 和 $g_R\in G_R$ 都等于某个 $a+\ast_b$。则：
- 设存在满足条件 I 和条件 II 的数，则 $g$ 等于最简单的这样的数。
- 条件 I：对于每个 $a+\ast_b\in G_L$。$>a$。（若 $b=0$）$\ge a$。（若 $b\neq0$）
- 条件 II：对于每个 $a+\ast_b\in G_L$。$<a$。（若 $b=0$）$\le a$。（若 $b\neq0$）
- 否则，显然 $G_L,G_R$ 非空。若 $G_L$ 的 $a$ 有最大元 $\ell$，$G_R$ 的 $a$ 有最小元 $r$，若 $\ell=r$，设 $P=\{b|\ell+\ast_b\in G_L\}$，$Q=\{b|r+\ast_b\in G_R\}$。若 $\operatorname{mex}(P)=\operatorname{mex}(Q)$，设 $c=\operatorname{mex}(P)=\operatorname{mex}(Q)$，则 $g=\ell +\ast_c$。
**证明.**
根据化简定理，前者显然。考虑后者。由推论 17.1，只需要保留 $G_L,G_R$ 中互不偏序的，也就是 $\ell+\ast_b$ 和 $r+\ast_b$，即可。换言之，不妨设 $g$ 为 $(\{\ell+\ast_p|p\in P\},\{\ell+\ast_q| q\in Q\}$，只需证 $g=\ell+\ast_c$ 即可。注意显然有 $c\neq 0$，否则 $\ell$ 满足前一种情况的适用条件。
$g\le \ell+\ast_c$。只需证不存在 $p\in P,\ell+\ast_p\ge \ell+\ast_c$，且不存在 $d<c$ 满足 $g\ge \ell +\ast_d$ 即可。前者因为 $c=\operatorname{mex}(P)$ 是显然的，而 $\ell+\ast_d$ 在 $g$ 的右集中，显然不成立。
$g\ge \ell +\ast_c$。只需证不存在 $q\in Q,\ell +\ast_q\le \ell+\ast_c$，且不存在 $d<c$ 满足 $g\le \ell+\ast_d$ 即可。前者因为 $c=\operatorname{mex}(Q)$ 是显然的，而 $\ell+\ast_d$ 在 $g$ 的左集中，显然不成立。
---
好！这样就可以计算出所有状态的值，计算答案了。注意实际上 $c=0$ 放到后一种情况算也没有问题。等等，以上最后一个定理似乎没有覆盖所有情况……实际上，在这些情况下结果就不再是 $a+\ast_b$ 了，比如 $(\{1\},\{0\})$，$(\{1\},\{-1\})$，$(\{0\},\{\ast\})$ 这些。这些就等到下次再说吧……
贴个代码：
```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
typedef long long ll;
using namespace std;
struct frac{
ll p,q;
frac(ll P=0,ll Q=1)
{
p=P;q=Q;
int d=int(min(__builtin_ctzll(p),__builtin_ctzll(q)));
p>>=d;q>>=d;
}
};
const frac NINF=-2000,INF=2000;
const frac NEPS=frac(-1,2048),EPS=frac(1,2048);
bool operator<(const frac&x,const frac&y)
{
ll r=max(x.q,y.q);
ll a=x.p;if(x.q!=r)a<<=int(__builtin_ctzll(r)-__builtin_ctzll(x.q));
ll b=y.p;if(y.q!=r)b<<=int(__builtin_ctzll(r)-__builtin_ctzll(y.q));
return a<b;
}
bool operator<=(const frac&x,const frac&y)
{
ll r=max(x.q,y.q);
ll a=x.p;if(x.q!=r)a<<=int(__builtin_ctzll(r)-__builtin_ctzll(x.q));
ll b=y.p;if(y.q!=r)b<<=int(__builtin_ctzll(r)-__builtin_ctzll(y.q));
return a<=b;
}
frac operator+(const frac&x,const frac&y)
{
ll r=max(x.q,y.q);
ll a=x.p;if(x.q!=r)a<<=int(__builtin_ctzll(r)-__builtin_ctzll(x.q));
ll b=y.p;if(y.q!=r)b<<=int(__builtin_ctzll(r)-__builtin_ctzll(y.q));
return frac(a+b,r);
}
bool operator==(const frac&x,const frac&y)
{
return x.p==y.p&&x.q==y.q;
}
struct game{
frac a;
int b;
bool l_second_win()
{
return (0<a)||(a==0&&b==0);
}
game(frac x=0,int y=0)
{
a=x;b=y;
}
};
game operator+(const game&gmx,const game&cyx)
{
return game(gmx.a+cyx.a,gmx.b^cyx.b);
}
game dp[21006];
bool valid[21006];
int a[13];
int counter,notnum;
const int pw3[10]={1,3,9,27,81,243,729,2187,6561,19683};
#define CHK(x,y,z) (a[x]!=0&&a[x]==a[y]&&a[y]==a[z])
void init()
{
rep(i,pw3[9])
{
rep(j,9)
{
a[j]=i/pw3[j]%3;
}
if(CHK(0,1,2)||CHK(3,4,5)||CHK(6,7,8)||CHK(0,3,6)||CHK(1,4,7)||CHK(2,5,8)||CHK(0,4,8)||CHK(2,4,6))
valid[i]=false;
else
valid[i]=true;
}
per(i,pw3[9])
{
if(!valid[i]) continue;
frac L=NINF,R=INF;
set<int> LS,RS;
LS.clear();RS.clear();
int count=0;
rep(j,9)
{
if((i/pw3[j])%3==0)
{
++count;
if(valid[i+pw3[j]])
{
frac qwq=dp[i+pw3[j]].a;int qaq=dp[i+pw3[j]].b;
if(L<qwq)
{
L=qwq;
LS.clear();LS.insert(qaq);
}
else if(L==qwq)
{
LS.insert(qaq);
}
}
if(valid[i+pw3[j]*2])
{
frac qwq=dp[i+2*pw3[j]].a;int qaq=dp[i+2*pw3[j]].b;
if(qwq<R)
{
R=qwq;
RS.clear();RS.insert(qaq);
}
else if(R==qwq)
{
RS.insert(qaq);
}
}
}
}
if(L<R)
{
if(LS.find(0)==LS.end()) L=L+NEPS;
if(RS.find(0)==RS.end()) R=R+EPS;
frac ret=0;
if(L<0&&0<R) ret=0;
else if(R==INF) ret=L.p/L.q+1;
else if(L==NINF) ret=-(-R.p)/R.q-1;
else
{
if(L<0)
{
for(ll u=1;;u<<=1)
{
if(L<-(-R.p)/R.q-1)
{
ret=frac(-(-R.p)/R.q-1,u);break;
}
L=L+L;R=R+R;
}
}
else
{
for(ll u=1;;u<<=1)
{
if(L.p/L.q+1<R)
{
ret=frac(L.p/L.q+1,u);break;
}
L=L+L;R=R+R;
}
}
}
dp[i].a=ret;dp[i].b=0;
}
else
{
dp[i].a=L;
for(int j=0;;++j)
{
if(LS.find(j)!=LS.end()&&RS.find(j)!=RS.end()) continue;
dp[i].b=j;break;
}
}
}
}
int t,n,cur;
string s0,s1,s2;
game result;
void Q()
{
result=game(0,0);
cin>>n;
rep(i,n)
{
cur=0;
cin>>s0>>s1>>s2;
rep(j,3)
{
if(s0[j]!='.') cur+=pw3[j];
if(s0[j]=='x') cur+=pw3[j];
if(s1[j]!='.') cur+=pw3[j+3];
if(s1[j]=='x') cur+=pw3[j+3];
if(s2[j]!='.') cur+=pw3[j+6];
if(s2[j]=='x') cur+=pw3[j+6];
}
result=result+dp[cur];
}
if(result.l_second_win()) cout<<"Bob\n";
else cout<<"Alice\n";
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
init();
cin>>t;while(t--)Q();
return 0;
}
```