ICPC 2025 西安区域赛 M. Mystique as Iris 题解¶

https://qoj.ac/contest/2562/problem/14693

题目大意¶

给定一个长度为 $n$（$2 \le n \le 10^6$）的数组 $a$ 和一个整数 $m$（$1 \le m \le 10^8$），其中每个元素在 $[1,m]$ 范围内或者用 $-1$ 表示缺失的元素，需要用 $[1,m]$ 之间的任意整数来替换 $-1$。

在替换后的数组上，可以执行操作，对于每次操作：

选择数组中相邻的两个元素，将其中一个减 $1$，并将另一个直接变为 $0$。
移除数组中所有的 $0$。

如果一个数组能在有限次操作后（包括零次）被完全清空（变成空序列），则称该数组为“神秘的（mystic）”。

计算有多少种不同的替换方案，使得最终得到的数组是神秘的，答案对 $10^9+7$ 取模。

例如：$n=2$，$m=2$，数组为 $[-1, -1]$，有 $3$ 种替换方案是神秘的：$[1, 1] [1, 2] [2, 1]$。

题目分析¶

先去寻找“非神秘数组”的特征，神秘数组的替换方案数即为总方案数减去非神秘数组的方案数。

分析这种“移除”操作的本质：

操作本质上是用一个元素去“移除”其相邻的元素。每移除一个元素，它自身的代价是减 $1$。
如果一个元素 $x$ 最终被置为 $0$ 并移除，它必须满足以下两种情况之一：
它的初始值就是 $1$，在某次操作中自身减 $1$ 变为 $0$，相邻元素直接变为 $0$；
它通过不断移除相邻元素（共移除 $x-1$ 个其他元素），使其自身数值降为 $1$，最后自身减 $1$ 变为 $0$，相邻元素直接变为 $0$。
这意味着：如果一个元素的初始值 $x \ge n$，那么即使它移除了数组中所有其他的 $n-1$ 个元素，它的数值依然 $\ge 1$，永远无法变为 $0$。因此，数值 $\ge n$ 的元素可以被视为“无法被完全移除的大值元素”。
元素 $1$ 所在的位置决定了它是否能清空整个数组：
位于边缘的 $1$： 它可以作为最终的移除条件。我们可以先让除该 $1$ 之外的其他所有元素相互执行操作，最终合并为一个唯一存活的元素（数组从 $[1,X,X,X]$ 变成了 $[1,Y]$），最后再利用这个边缘的 $1$ 与该残留元素互相移除，从而清空整个数组。
位于中间的 $1$： 如果 $1$ 被夹在两个“无法被移除的大值元素”之间（例如 $[n, 1, n]$），它只能选择与其中一侧的元素互相移除（数组从 $[X,1,X]$ 变成了 $[X]$），这必然会导致另一侧的大值元素继续保留。
对于初始数值在 $1<x<n$ 之间的元素，它总是能够通过移除部分元素使自己降为 $1$，并且保证在它降为 $1$ 时，数组中至少还有一个剩余元素供其进行最后一次移除。因此，只要数组中存在哪怕一个 $1<x<n$ 的元素，这个数组必定是可以被清空的（即神秘的）。

通过上述严格的推导可以得出，一个数组是非神秘的（即必定无法被清空），仅存在以下两种情况：

情况一：常规非神秘序列（可通过 DP 计算）

当且仅当数组同时满足以下所有条件时，它无法被清空：

数组中的所有元素要么是 $\ge n$，要么是 $1$。
所有的 $1$ 都不能出现在数组的两端（即 $a_1 \neq 1$ 且 $a_n \neq 1$）。
数组中不能有相邻的 $1$。

情况二：奇数长度下全部由 $1$ 组成的数组

如果数组中不存在任何 $\ge n$ 的数字，而是全部由 $1$ 组成的数组，且数组长度 $n$ 为奇数时，移除到最后必然会剩下一个孤立的 $1$ 无法移除（数组从 $[1, 1, 1]$ 变成了 $[1]$），这也是一种非神秘数组。

动态规划¶

针对情况一，定义：

$dp[i][0]$：表示前 $i$ 个元素构成的非神秘前缀中，第 $i$ 个元素为 $X$（即 $X \ge n$）的合法方案数。
$dp[i][1]$：表示前 $i$ 个元素构成的非神秘前缀中，第 $i$ 个元素为 $1$ 的合法方案数。

状态转移¶

填充 $X \ge n$ 的可行方案数记为 $cnt_0$：若 $a_i = -1$，则有 $\max(0, m - n + 1)$ 种选择；若 $a_i$ 为已知值，仅当 $a_i \ge n$ 时方案数为 $1$，否则为 $0$。
填充 $1$ 的可行方案数记为 $cnt_1$：若 $i$ 位于两端（$i=1$ 或 $i=n$），规定 $cnt_1 \leftarrow 0$；若位于中间位置且 $a_i = -1$ 或 $a_i = 1$，方案数为 $1$，否则为 $0$。
当前元素为 $X$，前一个元素可以是 $X$ 或 $1$：

$dp[i][0] = (dp[i-1][0] + dp[i-1][1]) \times cnt_0 \pmod{10^9+7}$

由于不能有相邻的 $1$，所以 $1$ 的前一个元素必须是 $X \ge n$：

$dp[i][1] = dp[i-1][0] \times cnt_1 \pmod{10^9+7}$

最终答案计算¶

累计总方案数 $tot$： $$ tot=\prod_{i=1}^{n} t_i,\quad t_i= \begin{cases} m, & a_i=-1,\ 1, & a_i\ne -1. \end{cases} $$
情况一对应的非神秘数组数量为 $dp[n][0]$。
额外检查全部由 $1$ 组成的数组且 $n$ 为奇数，则将非神秘数组的数量额外加 $1$。
最终用总方案数 $tot$ 减去修正后的非神秘数组总数，再对 $10^9+7$ 取模，即为神秘数组的数量。

完整代码¶

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

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

int n, m;
bool sgn = true;
ll dp[N][2];
ll tot = 1;

//~ 数组中的所有元素要么是 >= n，要么是 1。
//~ 所有的 1 都不能出现在数组的两端（存在特例）。
//~ 数组中不能有相邻的 1。

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (a == -1) {
            tot = tot * m % MOD;
        }
        if (a != -1 && a != 1) {
            sgn = false;
        }

        int cnt_0 = 0;
        if (a == -1) {
            cnt_0 = max(0, m - n + 1);
        } else if (a >= n) {
            cnt_0 = 1;
        }

        int cnt_1 = 0;
        if (1 < i && i < n) {
            if (a == -1) {
                cnt_1 = 1;
            } else if (a == 1) {
                cnt_1 = 1;
            }
        }

        if (i == 1) {
            dp[1][0] = cnt_0;
            dp[1][1] = 0;
        } else {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD * cnt_0 % MOD;
            dp[i][1] = dp[i - 1][0] * cnt_1 % MOD;
        }
    }

    cout << (tot - dp[n][0] - (n % 2 && sgn) + MOD) % MOD << endl;

    return 0;
}