【题意】：两个人在玩数字游戏，规则如下：有2~20这19个数，每个回合每个人轮流取走一个数k，k取走后k的所有倍数都不可以再取，并且任意两个不可取的数的和也不可以取。给出当前的合法局面，问先手是否必胜，若必胜输出最优操作。

【题解】：考虑到一共只有19个数字，可以用状态压缩。然后在博弈树上记忆化搜索即可，找到第一个必胜局面就可以跳出了。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define MAX 524287
19 int n, x[20];
20 int dp[MAX+10];
21 vector<int> vec;
22 
23 void getmask(int &tmp, int &forbid, int x) {
24     for(int i = x; i <= 20; i += x) {
25         if(tmp & (1<<(i-2))) {
26             tmp &= ~(1<<(i-2));
27             forbid |= (1<<(i-2));
28         }
29     }
30     for(int i = 2; i <= 20; i++) {
31         if(forbid & (1<<(i-2)))
32             for(int j = i + 1; j <= 20 - i; j++) {
33                 if((forbid & (1<<(j-2))) && (tmp & (1<<(i+j-2)))) {
34                     tmp &= ~(1<<(i+j-2)), forbid |= (1<<(i-2));
35                 }
36             }
37     }
38 }
39 
40 bool g(int mask, int forbid) {
41     if(dp[mask] != -1) return dp[mask];
42     for(int i = 2; i <= 20; i++) {
43         if(mask & (1<<(i-2))) {
44             int nmask = mask, nforbid = forbid;
45             getmask(nmask, nforbid, i);
46             if(!g(nmask, nforbid)) return dp[mask] = 1;
47         }
48     }
49     return dp[mask] = 0;
50 }
51 
52 void init() {
53     memset(dp, -1, sizeof(dp));
54     dp[0] = 0;
55 }
56 
57 int main() {
58     int T, Case = 1;
59     scanf("%d", &T);
60     init();
61     while(T--) {
62         vec.clear();
63         scanf("%d", &n);
64         int mask = 0;
65         for(int i = 0; i < n; i++) {
66             scanf("%d", &x[i]);
67             mask |= (1<<(x[i]-2));
68         }
69         int forbid = MAX & ~mask;
70         for(int i = 0; i < n; i++) {
71             int nmask = mask, nforbid = forbid;
72             getmask(nmask, nforbid, x[i]);
73             if(!g(nmask, nforbid)) vec.pb(x[i]);
74         }
75         printf("Scenario #%d:\n", Case++);
76         if(vec.size()) {
77             sort(vec.begin(), vec.end());
78             printf("The winning moves are:");
79             for(int i = 0; i < vec.size(); i++) printf(" %d", vec[i]);
80             printf(".\n\n");
81         } else printf("There is no winning move.\n\n");
82     }
83     return 0;
84 }