Codeforces 455B. A Lot of Games(字典树上博弈)

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

Input

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn’t exceed 105. Each string of the group consists only of lowercase English letters.

Output

If the player who moves first wins, print “First“, otherwise print “Second” (without the quotes).

Examples
input

output

input

output

input

output

题意:给出n个字符串,要求两人轮流对一个空串进行操作,每次在末尾添加一个字符要求添加完后字符串必须是这n个字符串中的某个字符串的前缀。当某个人无法操作视为输。假如某个人在第i轮输掉,那么它在第i+1轮就是先手,那么问在第k轮的时候是第一轮的先手还是后手胜利。

假如只有一轮,我们只需要建立字典树,然后dfs推出来必胜必败态就可以了。但是现在是第k轮的胜败。所以我们必须要考虑在这一轮赢是否是真正优的决策。

假如先手只能输的话,那么他将会一直输,所以导致第k轮也是输。即第一轮的先手必败。

假如先手只能赢的话,那么他们有任何可以选择的余地,所以第k轮的胜负和k的奇偶性有关。

假如先手可以自己决定胜利还是输的话,那么他可以输掉前k-1轮,保证第k轮自己的先手然后获胜就行了。所以是还是第一轮先手必胜。

假如先手无法决定自己胜利还是输的话,那么就相当于后手可以决定胜负,那么先手必败。因为后手一定可以做出对自己有利的决策。

现在考虑状态如何转移:假如一个状态的后继都是只能输的状态,那么这个就是只能赢的状态。

假如一个状态的后继都是只能赢的状态,那么这个就是只能输的状态。

假如一个状态的后继中存在只能输和只能赢的后继,或者是他的后继中有无法自己决策输赢的情况,那么他就是可以自己决定胜负的状态。

同理自己无法决定胜负的状态一定是后继中只有可以自己决定胜负的状态。

然后dfs一下,可以求出字典树root的状态,然后讨论一下就好了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注