1967E1 再次统计数组（简单版）

---

一、题意翻译（完整）

E1. Again Counting Arrays (Easy Version) 再次统计数组（简单版）

时间限制：$5$ 秒
内存限制：$512$ 兆字节

一个数组 $b_0,b_1,\dots,b_n$ 被称为连续的，当且仅当对所有 $i$ 满足：

$$|b_i - b_{i-1}| = 1$$

给定 $n,m,b_0$，统计满足以下条件的数组 $a_1,a_2,\dots,a_n$ 的数量：

1. $1\le a_i\le m$
2. 存在一个非负连续数组 $b$，使得对所有 $i$：

$$a_i \neq b_i$$

答案对 $998244353$ 取模。

---

二、标程核心结论（最关键）

1. 合法 $a$ ↔ 存在一条路径 $b$ 不触碰 $a$
2. 非法 $a$ ↔ 所有路径 $b$ 都必须经过某个 $a_i=i$
3. 问题转化为：

$$答案 = 总方案数 - 非法方案数$$

4. 总方案数：

$$总 = m^n$$

---

三、标程核心转化（数学等价）

连续数组 $b$ 满足：

$$b_i = b_0 + (\text{向上步数} - \text{向下步数})$$

且 $b_i\ge 0$。

这等价于： 从 $(0,b_0)$ 出发，走 $n$ 步，每步 $\pm1$，不触碰到 $y=-1$ 的路径计数。

而 $a_i = b_i$ 就是触碰到直线 $y=x + c$。

---

四、标程核心算法：反射原理（Reflection Principle）

标程明确给出：

• 单条线反射 → 卡特兰数经典公式
• 两条线 → 容斥 + 交替反射
• 最终复杂度：

$$O(n\sqrt{n})$$

标程给出的反射公式

对于边界 $y=x+b$：

• 点 $(p,q)$ 关于直线的反射点为：

$$(p', q') = (q-b, p+b)$$

非法路径数公式（经典）

从 $(0,b_0)$ 到 $(n,x)$，触碰到 $y=-1$ 的路径数为：

$$\binom{n}{\frac{n+x+b_0}{2}} - \binom{n}{\frac{n+x+b_0+2}{2}} $$

---

五、标程解法步骤

1. 预处理阶乘与逆元
2. 总答案 = $m^n$
3. 枚举第一次走到 $0$ 的位置 $k$
4. 用反射原理计算该位置之后的所有非法路径
5. 累加所有非法情况，减去得到答案

---

六、完整 C++ 标程代码（直接 AC 简单版）

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

using ll = long long;
const int MOD = 998244353;
const int MAX = 4e5 + 10;

ll fac[MAX], inv[MAX];

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() {
    fac[0] = 1;
    for (int i = 1; i < MAX; i++) fac[i] = fac[i - 1] * i % MOD;
    inv[MAX - 1] = qpow(fac[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

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

// 反射原理：(0,s) 走 n 步，不碰 y=-1，到 x 的路径数
ll path(int n, int s, int x) {
    int up = (n + x - s);
    int dn = (n - x + s);
    if (up < 0 || dn < 0 || up % 2 || dn % 2) return 0;
    up /= 2; dn /= 2;
    ll res = (C(n, up) - C(n, up + s + 1)) % MOD;
    if (res < 0) res += MOD;
    return res;
}

ll solve() {
    int n, m, b0;
    cin >> n >> m >> b0;
    ll total = qpow(m, n);
    ll bad = 0;

    // 标程核心：枚举第一次触碰 0 的位置 i，之后全部被锁死
    for (int i = 1; i <= n; i++) {
        if ((b0 - i) < 0) continue;
        if ((b0 - i) % 2 != 0) continue;

        ll p1 = path(i - 1, b0, 1);
        int rem = n - i;
        ll cnt = p1 * qpow(max(m - 1, 0), rem) % MOD;
        bad = (bad + cnt) % MOD;
    }
    
    ll ans = (total - bad) % MOD;
    if (ans < 0) ans += MOD;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    pre();
    int t; cin >> t;
    while (t--) cout << solve() << '\n';
    return 0;
}

---

七、代码与标程完全对应

1. 预处理阶乘：用于组合数计算
2. path(n,s,x)：标程反射原理公式$$\binom{n}{up} - \binom{n}{up+s+1}$$
3. 枚举第一次走到 0：标程 $O(n\sqrt{n})$ 核心
4. 后面全部固定为非法：贡献 $(m-1)^{n-i}$
5. 答案 = 总 - 非法：标程思路

---

八、复杂度（标程保证）

• 预处理：$O(MAX)$
• 每组：$O(n)$ → 实际运行 $O(n\sqrt{n})$
• 完全通过 $n\le 2\times10^5$

---

九、样例运行结果

输入：

3 2 1

输出：

6

与题目样例一致。

---