构造与证明：ICPC2025西安 M

首先如果一个数 ≥n\ge n，我们就直接记为 nn，这种数的特点是一定不能通过-1的操作来删掉。

首先请允许我证明只要存在 2∼n−12\sim n-1 内的数，就一定可以删光。

首先，每次操作只会减少1-2个数。

  1. 如果存在 n−1n-1，那它和每个数都操作就可以全部删光

  2. 如果存在 n−2n-2

    • 如果剩下的数（不包括 n−2n-2 这个数本身）存在一种操作恰好减少一个数，那样子此时序列长度 nn 减1，变成第一种情况，必然可以删光

    • 如果剩下的数无论如何操作都必须减少两个数，我们就让这个 n−2n-2 和任意一个相邻的数操作一次，把这个相邻的数删掉，而它本身减1。此时 nn 也减少了1，n−2n-2 也减少了1，还是处于当前的情况。

      一直减，直到 n=4n=4，那么此时只会有这几种情况：

      • 1 1 1 2 1 1 2 1 ：先操作(1,2)变空，再操作(1,1)变空
      • 1 1 2 2 1 2 1 2 2 1 1 2 ：操作两次(1,2)变空
      • 2 2 2 1 2 2 1 2：先操作(2,2)变成一个1，再操作(1,2)变成一个1，再操作(1,1)变空
      • 2 2 2 2：先操作两次(2,2)变成两个1，再操作一次(1,1)变空

  3. 如果存在小于等于 n−3n-3 的数，我们不动它，剩下的随便操作，每次减1个或2个数，迟早会变成上面两种情况之一

接下来，我们会说明只有以下两种情况是不行的

  1. 整个序列只由 11 和 nn 组成，开头结尾都是 nn，且中间没有连续的1
  2. 如果 nn 为奇数，则需要额外增加一种全是1的情况

第二种情况显然。

第一种情况，我们先证明其一定不行。

考虑如果有连续的 nn，肯定可以通过相邻之间互相抵消的方式变成一个非 11 的数，最后整个序列必然长出这样：

1
a 1 b 1 c 1 d 1 e 1 f 1

如果我们把序列长度缩短视为 nn 减小的话，那么 abcdef≥nabcdef \ge n 是始终成立的。

而最终每个1只能消除一个相邻的数，那样子最后必然有一个数不能被消除。

接下来我证明由相邻的1必然可行。

首先连续的 nn 必然可以缩减成一个数。

假设现在只有一个位置有相邻的1：

1
a 1 b 1 c 1 1 d 1 e 1 f 1

我们直接划分成左右，分别拿1进行消去即可。

如果有更多的1，我们可以随便让它和旁边的数操作，每次可以只减少一个数，那样子也是可以规约到上面这种情况的。

image-20261002143729861

上面的情况讨论完，计数直接dp即可，这个不用讲。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std; 
#ifdef LOCAL 
	#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else 
	#define debug(...) void(0)
#endif
#define int long long
int read() {
	int x; 
	scanf("%lld", &x); 
	return x; 
}
#define pb push_back
#define N 1000010
//#define M
#define mo (int)(1e9 + 7)
int n, m, i, j, k, T; 
int a[N], dp[N][2], flg, sum, ans; 

signed main() {
	#ifdef LOCAL
		freopen("in.txt", "r", stdin); 
		freopen("out.txt", "w", stdout); 
	#endif 
	n = read(); m = read(); sum = 1; 
	for(i = 1; i <= n; ++i) {
		a[i] = read(); 
		if(a[i] == -1) sum = sum * m % mo; 
		if(a[i] > 1 && a[i] <= n - 1) flg = 1; 
	}
	if(flg) return printf("%lld", sum), 0; 
	dp[1][0] = 1; 
	for(i = 2; i < n; ++i) {
		if(a[i] != -1) {
			if(a[i] == 1) dp[i][1] = dp[i - 1][0]; 
			else dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mo; 
			continue; 
		}
		if(m >= n) dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (m - n + 1) % mo; 
		dp[i][1] = dp[i - 1][0]; 
//		debug("%lld %lld\n", dp[i][0], dp[i][1]); 
	}
	ans = (dp[n - 1][0] + dp[n - 1][1]) % mo; 
	if(a[1] == -1) {
		if(m >= n) ans = ans * (m - n + 1) % mo; 
		else ans = 0; 
	}
	if(a[n] == -1) {
		if(m >= n) ans = ans * (m - n + 1) % mo; 
		else ans = 0; 
	}
	if(a[1] == 1) ans = 0; 
	if(a[n] == 1) ans = 0; 
	if(n & 1) {
		for(i = 1; i <= n; ++i) 
			if(a[i] > 1) break; 
		if(i > n) ++ans; 	
//		debug("%lld | %lld", ans, sum); 
		ans = sum - ans; ans = (ans % mo + mo) % mo; 
		printf("%lld", ans % mo); 
		return 0; 
	}
	ans = sum - ans; ans = (ans % mo + mo) % mo; 
	printf("%lld", ans % mo); 
	return 0; 
}