原题

题意

给定 $n$ 个 01 串的集合和长度 $L$，玩游戏，每次向集合中加入一个长不大于 $L$ 的 01 串，要求所有时刻集合内任意两串互不为前缀，无法加入则输掉游戏，问先手或后手谁有必胜策略。

1.字典树

通过字典树我们可以找出所有可加入字符串的情况，对于度数为 $1$ 的节点，其没有边的字符处可以加入对应字符串。对于一个位置，如果对应的前缀长为 $x$，可以加入的字符串中长度为 $L$ 的有 $2^{L - x - 1}$ 个，我们若加入一个长为 $y(y > x)$ 的字符串，会形成 $(y - x)$ 组，第 $i$ 组对应 $2^{L - i - x - 1}$ 个长为 $L$ 的串，至此这道题变成了二进制问题。

2.结论：两个匹配的大小相同的组各不影响胜负

可以发现，两个匹配相同大小的组是对称的，去掉两组后，可以发现：

1. 如果去掉后当前手必胜时不会动这两组。
2. 如果去掉后当前手必败，那么他如果对任意一组操作，对手可以向另一组做同样操作，仍然无法挽回局面。

3.基于结论的状压动规与最终结论

我们可以跟据如上结论设计状压动规，代码如下：

#include<cstdio>
#include<iostream>
#include<bitset>
using namespace std;
int dp[(1 << 16)];
int main(){
	dp[0] = 0;
	for(int i = 1; i < (1 << 16); i ++){
		for(int j = 1; j <= 16; j ++){
			if((i >> j - 1) & 1){
				int o = 0;
				for(int k = j; k > 0; k --){
					o = o | (1 << k - 1);
					dp[i] = dp[i] || ((!dp[i ^ o]) & 1);
				}
			}
		}
	}
}

状压 DP 是 $\operatorname{O}(L^2 2^L)$，无法解决这道题，但是我们对于 $L \le 9$ 的情况打表，由数据知大部分情况下先手胜，我们试图找后手胜的情况。

我们将后手胜的情况抓出来找规律，借助数据思考知，后手有必胜策略当且仅当对任意 $k \ge 0$，大小为 $2 ^ {2 ^ k - 1}$ 的组数为偶数，否则先手胜，验证知是否符合条件的情况中符合条件的状态操作后必然不符合条件，而不符合条件的状态能一步操作变成符合条件的情况，且最终失败状态符合条件，故结论正确。

比如对于先手胜的情况 $1,4,16$，我们一步操作：

1. 去掉 $16$。
2. 对于 $2^4$ 的倍数，原先多了 $16$，为奇数，现在变成了偶数，$2^3$ 同理。
3. 对于 $2^2$，变成了奇数，我们改为操作成 $1,4,12,13,14,15$。
4. 对于 $2^1$，也变成了奇数，改为操作变成 $1,4,10,11,12,13,14,15$。
5. $2^0$ 没问题现在变成了符合对手必输的情况。
6. 我们按类似方法构造，可以验证，甚至证明这个结论。

效率

我们得到了大小不超过 $\sum |s_i|$ 的字典树,统计时考虑对每一个节点 $v$ 空边，当 $2 ^ k|L - len_v$ 时有一组大小 $2 ^ {2 ^ k - 1}$ 的组，暴力处理不会超过 $\log L$ 次，故为 $\operatorname{O}(\sum {|s_i|} \log v)$，可以通过。

代码

#include<cstdio>
using namespace std;
int n,cst[63],cnt = 1;
long long L;
struct node{
	int len,ch[2];
	node(int l = 0){
		len = l;
		ch[0] = ch[1] = 0;
	}
}nd[100009];
char c[100009];
void add(int u,int v){
	if(c[v] == '\0')
		return;
	bool p = (c[v] - '0');
	if(nd[u].ch[p] == 0)
		nd[u].ch[p] = ++cnt,nd[cnt].len = v + 1;
	add(nd[u].ch[p],v + 1);
}
void srh(int u){//统计时叶子节点生成两个无效相同大小组，可视作额外两个匹配的组，不影响结果，无需特判 
	if(nd[u].ch[0] == 0){
		int cnt = 0;
		long long o = L - nd[u].len;
	//	printf("%d\n",o);
		if(o > 0){
			cst[0] ^= 1;
			while(!(o & 1)){
				o = o >> 1;
				cnt ++;
				cst[cnt] ^= 1;
			}
		}
	}
	else
		srh(nd[u].ch[0]);
	if(nd[u].ch[1] == 0){ 
		int cnt = 0;
		long long o = L - nd[u].len;
		//printf("%d\n",o);
		if(o > 0){
			cst[0] ^= 1;
			while(!(o & 1)){
				o = o >> 1;
				cnt ++;
				cst[cnt] ^= 1;
			}
		}
	}
	else
		srh(nd[u].ch[1]);
}
int main(){
	scanf("%d %lld",&n,&L);
	for(int i = 1; i <= n; i ++){
		scanf(" %s",c);
		add(1,0);
	}
	srh(1);
	bool flg = false;
	for(int i = 0; i < 63; i ++)//结论 
		flg = flg || cst[i];
	if(flg)
		puts("Alice");
	else
		puts("Bob");
} 

不超过 $70$ 行确实对初学者友好。