[??记录]AT3727 [ARC087C] Prefix-free Game
command_block
2021-05-10 10:21:29
**题意** ： 本题中，字符集为 $\{\texttt{0},\texttt{1}\}$。
给出 $L$ ，定义一个字符串集合 $S$ 是好的，当且仅当 ：
- $S$ 中的字符串长度在 $1\sim L$ 之间。
- $S$ 中的任意两个字符串，都不能满足一者为另一者的前缀。
给出一个好的字符串集合 $S$。
A,B 博弈。两人轮流操作，每次可以向 $S$ 中加入一个字符串，无法操作者输。
问是否先手必胜。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
我们先用 $S$ 内的字符串建立字典树。
那么，每个串的前缀和子树都不能再选择，剩下的区域均为满二叉树。
考虑使用 $\rm SG$ 函数。
记层数为 $h$ 的满二叉树的 $\rm SG$ 值为 $f[h]$。
利用 $\text{Muti-SG}$ 的分析技巧，不难列出递推式 ：
$$
\begin{aligned}
f[h]=&{\rm mex}\Big\{\\
&0,\\
&f[h-1],\\
&f[h-1]\oplus f[h-2],\\
&f[h-1]\oplus f[h-2]\oplus f[h-3]\\
&\cdots\\
&f[h-1]\oplus f[h-2]\oplus ... \oplus f[1]\\
\Big\}&\\
\end{aligned}
$$
打表可以发现 $f[h]={\rm lowbit}(h)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 100500
#define ll long long
using namespace std;
struct Node{int t[2];}a[MaxN];
#define lbit(x) ((x)&-(x))
ll ans,L;
void dfs(int u,int dep)
{
if (!u){ans^=lbit(L-dep+1);return ;}
dfs(a[u].t[0],dep+1);dfs(a[u].t[1],dep+1);
}
int n,tn;char s[MaxN];
int main()
{
scanf("%d%lld",&n,&L);tn=1;
for (int t=1;t<=n;t++){
scanf("%s",s);
int len=strlen(s),u=1;
for (int i=0;i<len;i++){
s[i]-='0';
if (!a[u].t[s[i]])a[u].t[s[i]]=++tn;
u=a[u].t[s[i]];
}
}dfs(1,0);
printf(ans ? "Alice" : "Bob");
return 0;
}
```