ARC087C Prefix-free Game

发表于 更新于 分类于 ， ， 阅读次数：

题意：本题中，字符集为 。

给出 ，定义一个字符串集合 是好的，当且仅当 ：

  • 中的字符串长度在 之间。

  • 中的任意两个字符串，都不能满足一者为另一者的前缀。

给出一个好的字符串集合 。

A 和 B 博弈。两人轮流操作，每次可以向 中加入一个字符串，无法操作者输。

问是否先手必胜。

，时限 。

我们先用 内的字符串建立字典树。

那么，每个串的前缀和子树都不能再选择，剩下的区域均为满二叉树。

考虑使用 函数。

记层数为 的满二叉树的 值为 。

利用 的分析技巧，不难列出递推式 ：

打表可以发现 。