（位运算 + 博弈DP + 枚举所有状态）

这道题n ≤ 20，m ≤ 2，天然适合用二进制状态压缩DP，把每堆石子映射成一个 bit，暴力枚举所有局面，再用博弈DP求最终结果。

---

0. 核心结论（先记住）

1. m=1：所有堆都是 1，答案恒为 1。
2. m=2：
   • 把每堆石子映射成二进制：1→0，2→1。
   • 用 dp[turn][len][mask] 表示：当前长度为 len、状态为 mask、当前玩家为 turn 时，最终留下的是 0 还是 1。
   • 枚举所有 $2^n$ 种局面，把结果求和即可。

---

1. 状态定义（标程核心）

映射规则

$$a_i = 1 \implies bit=0,\quad a_i=2\implies bit=1$$

DP 状态

dp[ player ][ current_length ][ mask ]

• player = 0：Bob 回合（想让最终值 = 0）
• player = 1：Alice 回合（想让最终值 = 1）
• current_length：当前剩下多少堆
• mask：当前石子堆的二进制状态

转移规则

• Alice（max 玩家）：只要有一个操作能让结果 = 1，结果就是 1。
• Bob（min 玩家）：必须所有操作结果都是 1，结果才是 1。

---

2. 转移公式（严格数学）

设当前长度 $i$，可删除的位置集合为 $good$：

Bob 玩家（player=0）

$$dp[0][i][mask] = \bigwedge_{x \in good} dp[1][i-1][mask'] $$

（所有后继都为 1，结果才是 1）

Alice 玩家（player=1）

$$dp[1][i][mask] = \bigvee_{x \in good} dp[0][i-1][mask'] $$

（有一个后继为 1，结果就是 1）

其中 $mask'$ 是删除第 $x$ 位后的新掩码。

---

3. 最终答案计算

对所有 $2^n$ 个二进制状态：

$$\text{答案} = \sum_{mask=0}^{2^n-1} \big(1 + dp[1][n][mask]\big) $$

• $dp=0 \implies$ 最终值 = 1
• $dp=1 \implies$ 最终值 = 2

---

4. 标程代码逐行详解

（1）核心工具函数：删除某一位

int removebit(int n, int bit) {
    int filtermask = (1 << 22) - (1 << bit);
    return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1));
}

作用：删除二进制 n 的第 bit 位，后面的位自动前移，模拟题目中删除后重新编号的规则。

（2）m=1 特判

if(m==1){
    cout << 1 << "\n";
    continue;
}

只有一种局面，答案恒为 1。

（3）DP 初始化

if (i == 1) {
    for (int j = 0; j <= 1; j++)
        for (int k = 0; k <= 1; k++)
            dp[j][i][k] = k;
}

只剩一堆时，结果就是这堆本身的值。

（4）DP 转移（核心）

for (auto x : good) {
    if (x <= i) {
        int finmsk = removebit(msk, x - 1);
        ans0 &= dp[1][i - 1][finmsk];  // Bob：全部AND
        ans1 |= dp[0][i - 1][finmsk];  // Alice：全部OR
    }
}
dp[0][i][msk] = ans0;
dp[1][i][msk] = ans1;

（5）统计答案

mint finans = 0;
for (int r = 0; r < (1<<n); r++) {   
    finans += 1 + dp[pl][n][r];
}
cout << finans << endl;

---

5. 时间复杂度

$$O(n \cdot 2^n)$$

• $n\le 20,\ 2^{20}=1048576$
• 完全符合题目限制。

---

6. 极简记忆口诀

1. m=1 直接输出 1
2. m=2 把局面压成二进制 mask
3. DP 按博弈规则转移：Alice 取 OR，Bob 取 AND
4. 枚举所有 mask 求和
5. 答案 = 总个数 + 1 的个数

---