用f[i]表示有i根火柴时，当前人是赢还是输，那么f[i]是只与f[i-1], f[i-p[1]], f[i-p[2]], ... f[i-p[m]]有关的，如果这些状态都是赢，那么f[i]就是输，否则f[i]是赢。
　　直接这样递推到N就要TLE了。但考虑距离f[i]最远且与之相关的点是f[i-max(p[i])]，把他们之间的状态连起来，写成(f[i-max(p[i])],...,f[i-1],f[i])这样，f中用0/1表示输赢，则连起来的状态是个二进制数，如果这个二进制数重复出现，则整个f序列就会出现循环。循环节的长度加上不循环部分的长度不会超过2^max(p[i])。
　　Submit 1: WA on 4。我用pos[x]=i（x是(f[i-9],...,f[i-1],f[i])对应的二进制数）表示(f[i-9],...,f[i-1],f[i])这个状态第一次在i这个位置出现，那么就有个边界值——pos[x]是不小于9的。另外，找到循环节后立刻退出递推即可。
　　Submit 2: WA on 4。循环节的长度加上不循环部分的长度应该是不超过2^max(p[i]+1)+max(p[i]+1)，程序实现中应该是1034。
　　Submit 3: WA on 4。把f中的状态连起来时，只需要(f[i-9],...,f[i-1])就够了。边界值——pos[x]是不小于10的，循环节的长度加上不循环部分的长度应该是不超过2^9+10+1。用pos[x]=i（x是(f[i-9],...,f[i-1])对应的二进制数）表示(f[i-9],...,f[i-1])这个状态第一次在i这个位置出现，当x在j位置再次出现时，表示i到j-1是循环节。题目中给出的P1,P2,...,Pm并不是有序的。
　　Submit 4: WA on 4。if (N<=l2) r=f[N]; 这句有问题，f[l2]没有意义。
　　Submit 5: WA on 4。r=f[(N-l1)%(l2-l1)+l1]; 这个也要改成 r=f[(N-l1)%(l2-1-l1)+l1]; 这里问题的原因跟Submit 4是一样的，l2并不是循环节末端，而是“超出末端”，循环节是l1...l2-1。
　　Submit 6: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int main()
{
    int K,N,m,p[9]={1},pos[512],x,l1,l2;
    bool f[524],r;
    scanf("%d",&K);
    for (;K;--K)
    {
        memset(pos,0,sizeof(pos)); memset(f,0,sizeof(f)); x=0; l1=0; l2=2;
        scanf("%d%d",&N,&m);
        for (int i=1;i<=m;++i) scanf("%d",&p[i]);
        sort(p,p+m+1);
        for (;!l1;++l2)
        {
            f[l2]=1;
            for (int j=0;j<=m && l2-p[j]>0 && f[l2];++j) f[l2]&=f[l2-p[j]];
            f[l2]=!f[l2];
            if (pos[x]) l1=pos[x];
            else if (l2>9) pos[x]=l2;
            x=(x<<1)&0x1ff|f[l2];
        }
        if (N<l2) r=f[N];
        else r=f[(N-l1)%(l2-1-l1)+l1];
        if (r) printf("FIRST PLAYER MUST WIN\n");
        else printf("SECOND PLAYER MUST WIN\n");
    }
    return 0;
}