English:

My DP is a little different form another Editorial’s.

Note that \(N \le 16\),so we can use Status Compression Dynamic Programming to solve it.

Assuming that \(f_{i,j}\) expresses if we have the status \(i\) and the last letter is \(j\),we can win or lose.

Note that \(f_{i,j}\) could be solved by all \(f_{k,l}\) while \(k\) isn’t belong \(i\) and \(s_k\)’s first letter is \(j\).if we have a \(f_{k,l}\) that \(f_{k,l}=1\),\(f_{i,j}\) will be \(0\),otherwise \(f_{i,j}\) will be \(1\).

Finally,the answer is First only if we have \(f_{2^i,S}=1\) that \(0<i<N\),\(S\) is the last letter in \(s_i\).

And we must DP in reverse order.

Chinese:

我的 DP 跟官方题解的有点不一样。

注意到 \(N \le 16\)，所以可以直接状压。

设 \(f_{i,j}\) 表示状态为 \(i\)，最后一个字母是 \(j\) 是否必胜。

枚举不在集合 \(i\) 中的元素 \(k\)，如果某一个 \(f_{k,l}=1\)，那么 \(f_{i,j}=0\)，否则 \(f_{i,j}=1\)。

最后，是第一个人胜利当且仅当存在 \(i\)，使 \(f_{2^i,S}=1\)，其中 \(S\) 表示 \(s_i\) 的末尾字母。

注意要倒着 DP。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=16;
int f[1<<N][27],n;
string s[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i=0;i<n;++i) cin>>s[i];
    for (int i=(1<<n)-1;~i;--i)
        for (int k=0;k<26;++k){
            int flg=1;
            for (int l=0;l<n;++l){
                if ((1<<l)&i) continue;
                if (s[l][0]!='a'+k) continue;
                if (f[i|(1<<l)][s[l][s[l].length()-1]-'a']){flg=0;break;}
            }
            f[i][k]=flg;
        }
    for (int i=0;i<n;++i)
        if (f[1<<i][s[i][s[i].length()-1]-'a']){
            cout<<"First\n";
            return 0;
        }
    cout<<"Second\n";
    return 0;
}