原题地址

题目描述

给定n个小写字母组成的字符串,有两个人用这些字符串玩游戏。游戏内容是轮流在一个空串末尾添加一个小写字母,使得它是n个字符串中某一个的前缀,直到一个人无法继续操作,TA就成为输家,下一轮游戏中输家先开始。

定义一次游戏为产生一次输家,问k次游戏后的胜者是先手还是后手?

样例

输入

输出

思路

先把这些串直接加进空串,然后建字典树,在树上DP,从叶子回溯到根。

二进制状态有4种,00和11代表结果和k相关,10代表先手赢,01代表后手赢。

叶子对父亲的贡献异或10之后和父亲的状态或一下就好了。

代码