cf455 B. A Lot of Games（字典树上博弈）

题意：

给定n个字符串。初始有个空串，两人轮流往串末尾每次加一个字符，要求任意时刻得到的字符串都是某个给定字符串的前缀。不能操作的人输。

现重复进行k次这个游戏，每次由上一次输的人先手，第k次游戏的胜者为最终胜者。问谁能赢

所有串长之和 \(\le 1e5\)

思路：

先只考虑单独的一次游戏。实际上是在一棵字典树上从根开始向下移动（定义一个虚根0），不能移动者输。

叶子节点没有儿子，为必败节点（记为 ansi=0）。然后从下往上递推每个节点的状态：

若某节点的儿子全是必胜点，则该节点为必败点；若某节点的儿子全是必败点，则该节点为必胜点（记为1）；

若某节点的儿子中既有必胜点又有必败点，则该节点为可控点（记为2）

（注意可控是最好的状态，应尽量使点可控；被控是最差的状态，应尽量避免）

若某节点的儿子全是可控点，则该节点为被控点（记为3）；若某节点的儿子中有一个被控点，则该节点为可控点；

若某节点的儿子全是必败和可控，则该节点必胜；若某节点的儿子全是必胜和可控，则该节点必败。

经过上面的递推可以算出 ans[0]，即单次游戏的状态。若单次游戏先手必败，则k次游戏先手必败；若单次游戏先手必胜，则k次游戏的胜负取决于k的奇偶性；

若单次游戏先手可控，则先手者可以让自己每次都先手，故先手必胜；若单次游戏先手被控则先手必败。

const int N = 1e5 + 5;
int n, k; string s;

int son[N][26], idx;
void add(string s)
{
    int p = 0;
    for(char x : s)
    {
        int u = x - 'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int ans[N];
void dfs(int u)
{
    ans[u] = 0;
    bool have[4] = {0,0,0,0}; //儿子有什么
    for(int i = 0; i < 26; i++)
    {
        int v = son[u][i];
        if(v) dfs(v), have[ans[v]] = 1;
    }
    if(have[3]) ans[u] = 2; //儿子有被控
    else if(have[0] && have[1]) ans[u] = 2; //有胜有败
    else if(have[0]) ans[u] = 1;
    else if(have[1]) ans[u] = 0;
    else if(have[2]) ans[u] = 3;
}

signed main()
{
    cin >> n >> k;
    while(n--) cin >> s, add(s);

    dfs(0);

    if(ans[0] == 2) puts("First");
    if(ans[0] == 3) puts("Second");
    if(ans[0] == 1) puts(k&1 ? "First" : "Second");
    if(ans[0] == 0) puts("Second");
}