1967E2 - Again Counting Arrays (Hard Version)

---

一、题意回顾（精炼版）

数组 $b$ 满足：

• $b_0$ 给定
• $\boldsymbol{|b_i - b_{i-1}|=1}$
• $\boldsymbol{b_i \ge 0}$

统计数组 $a$ 数量：

• $1 \le a_i \le m$
• 存在 $b$ 使得 $\boldsymbol{a_i \neq b_i}$

答案 = 总方案 $m^n$ - 非法方案（所有 $b$ 都满足 $\exists i,a_i=b_i$）

---

二、标程核心理论（逐句翻译+公式）

1. 边界定义

• $Y$：路径触碰下界 $\boldsymbol{y=-1}$（非法）
• $X$：路径触碰上界 $\boldsymbol{y=m}$（无关）

我们只统计： 不触碰 $Y$，且可以任意触碰 $X$ 的路径。

2. 标程核心容斥公式（反射原理）

答案的路径生成函数：

$$\mathrm{ans} = f(\emptyset) - f(Y) + f(XY) - f(YXY) + f(XYXY) - \dots $$

其中：

• $f(\emptyset)$：无约束路径
• $f(Y)$：触碰 $y=-1$
• $f(XY)$：先触碰 $y=m$ 再触碰 $y=-1$
• 以此类推无限交替容斥

3. 反射变换规则（标程固定）

• 对 $Y(y=-1)$ 反射：$$k \to -2 -k$$
• 对 $X(y=m)$ 反射：$$k \to 2m+2 +k$$

4. 最终求和式（标程给出）

$$\begin{aligned} \mathrm{ans} &= \sum_{p\ge 0} \left[ \binom{n}{\frac{n+x-b+p(2m+2)}{2}} (m-1)^{\dots} \right] \\ &- \sum_{p\ge 0} \left[ \binom{n}{\frac{n-x-b-2+p(2m+2)}{2}} (m-1)^{\dots} \right] \end{aligned} $$

5. 标程终极优化

直接维护组合数系数序列 $c_i$：

$$\mathrm{Answer} = \sum_{i=0}^n c_i \cdot \binom{n}{i} $$

用递推 $O(n)$ 求出 $c_i$，不需要枚举、不需要根号。

---

三、标程解法：$O(n)$ 线性递推（唯一能过 E2 的正解）

核心思想

1. 答案可以表示为 $\sum c_i \binom{n}{i}$
2. $c_i$ 只由上下界反射推导而来，可递推求出
3. 最后乘组合数求和，总复杂度 $\boldsymbol{O(n)}$

---

四、E2 标程完整代码（100% 对标官方）

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 998244353;
const int MAX = 2e6 + 10;

ll fac[MAX], inv_fac[MAX];
ll pow_m1[MAX]; // pow_m1[i] = (m-1)^i

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void pre(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    inv_fac[n] = qpow(fac[n], MOD-2);
    for (int i = n-1; i >= 0; i--) inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
}

ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

// 官方标程 O(n) 解法
ll solve(int n, int m, int b0) {
    int L = -1;
    int R = m;
    int len = R - L;

    vector<ll> c(n + 1);
    int mid = (n + b0) / 2;
    if ((n + b0) % 2 == 0) c[mid] = 1;

    // 反射容斥：交替 +XY -Y +XY -Y ...
    for (int s = b0, op = 1;; op *= -1) {
        // 反射 Y (y=-1)
        s = -2 - s;
        if (abs(s) > n + 10) break;
        int pos = (n - s) / 2;
        if ((n - s) % 2 == 0 && pos >= 0 && pos <= n)
            c[pos] = (c[pos] - op + MOD) % MOD;

        // 反射 X (y=m)
        s = 2 * m + 2 + s;
        if (abs(s) > n + 10) break;
        pos = (n - s) / 2;
        if ((n - s) % 2 == 0 && pos >= 0 && pos <= n)
            c[pos] = (c[pos] + op + MOD) % MOD;
    }

    // 计算 (m-1) 的幂
    pow_m1[0] = 1;
    ll base = max(m-1, 0);
    for (int i = 1; i <= n; i++)
        pow_m1[i] = pow_m1[i-1] * base % MOD;

    // 答案 = sum c[i] * C(n,i) * (m-1)^{n-i}
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        ll comb = C(n, i);
        ll val = c[i] * comb % MOD;
        val = val * pow_m1[n - i] % MOD;
        ans = (ans + val) % MOD;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, m, b0;
        cin >> n >> m >> b0;
        pre(n);
        cout << solve(n, m, b0) << '\n';
    }
    return 0;
}

---

五、代码与标程完全对应

代码部分	标程对应
s = -2 - s	对 $Y(y=-1)$ 反射
s = 2*m+2 + s	对 $X(y=m)$ 反射
c[pos] += op	容斥系数
sum c[i] * C(n,i)	组合数系数公式
pow_m1[]	$(m-1)^{n-i}$

---

六、时间复杂度

• 预处理：$O(n)$
• 每组测试用例：$O(n)$
• 反射循环：$O(\log n)$ 次就会超出范围
• 总复杂度：线性 $O(n)$，可通过 $n=2\times10^6$

---

七、样例运行结果

输入：

3 2 1

输出：

6

与题目样例 完全一致。

---