（状压DP + 组合计数 + 数位贡献法）

这是本题最难的核心思想：不枚举每个局面，而是统计「≥k」的方案数，用贡献法求和。 我会把英文题解 + 标程完整翻译成公式 + 中文逻辑，严格按你的要求排版。

---

0. 核心思想（最重要）

我们不求每个局面的最终值 $x$，而是求：

$$\text{答案} = \sum_{k=1}^m \,\text{【最终值} \ge k\text{ 的方案总数】} $$

这是大数求和通用技巧。

---

1. 二进制状态定义

对一个固定的 $k$：

• 若 $a_i \ge k$ → 二进制位 = $1$
• 若 $a_i < k$ → 二进制位 = $0$

一个局面 $\rightarrow$ 一个 mask（长度 $n$）。

---

2. 博弈 DP（和简单版完全一样）

状态

$$dp[p][i][mask]$$

• $p=1$：Alice 回合（max，想让结果=1）
• $p=0$：Bob 回合（min，想让结果=0）
• $i$：当前剩余堆数
• $mask$：当前二进制状态

转移

• Alice：只要一个操作能出 $1$ → 结果 $1$$$dp[1][i][mask] = \bigvee_{x \in good} dp[0][i-1][new\_mask] $$
• Bob：所有操作都必须出 $1$ → 结果 $1$$$dp[0][i][mask] = \bigwedge_{x \in good} dp[1][i-1][new\_mask] $$

---

3. 组合计数：cnt[r]

定义

$$cnt[r] = \text{恰好有 } r \text{ 个 1，且最终结果为 1 的 mask 数量} $$

含义

• 有 $r$ 堆满足 $\ge k$
• 有 $n-r$ 堆满足 $<k$

---

4. 对固定 k 的方案数公式

$$f(k) = \sum_{r=1}^n cnt[r] \cdot (k-1)^{n-r} \cdot (m-k+1)^r $$

• $(k-1)^{n-r}$：$n-r$ 堆取 $<k$ 的方案数
• $(m-k+1)^r$：$r$ 堆取 $\ge k$ 的方案数

---

5. 最终答案

$$\boxed{ans = \sum_{k=1}^m f(k)}$$

---

6. 标程代码逐段详解

（1）removebit：删除一位，模拟重编号

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

（2）DP 初始化（只剩一堆）

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

（3）DP 转移（核心）

for (auto x : good) {
    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;

（4）统计 cnt[r]：按 1 的个数计数

cnt[p][i][__popcount(msk)] += dp[p][i][msk];

（5）总答案计算

for (int r = 1; r <= n; r++)
    for(int k=1;k<=m;k++)
        ans += binpow(k-1,n-r) * binpow(m-k+1,r) % MOD * cnt[1][n][r] % MOD;

---

7. 时间复杂度

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

• $n\le 20$：状压可行
• $m\le 1e6$：线性遍历完全可行

---

8. 最简记忆口诀

1. 贡献法：答案 = $\sum_{k=1}^m P(x\ge k)$
2. mask：$\ge k$ 记为 1
3. 博弈DP：Alice OR，Bob AND
4. cnt[r]：r 个 1 且赢的 mask 数
5. 公式：乘组合数求和

---