Description
Link：CF2199H
给出一个数组 a1,…,an，其中 −1≤ai≤n。
对于每个 i (1≤i≤n)，求出 f([a1,…,ai])，其中 f(s) 对于数组 s 定义如下：
- 对于所有将 s 中的 −1 替换成 [0,n] 之间整数的不同方案，f(s) 为这些方案对应数组的 MEX 之和。
保证 −1 的数量不超过 300。
数据范围：1≤n≤2×105，−1≤ai≤n。
时空限制：5s / 512MiB。
Solution
乍一看有点像 「2026 杭电多校 2」1005. 减数游戏，但是本题要对每个前缀都求一次答案，不方便容斥。
首先将 mex(s) 转换成 ∑i=0n−1[mex(s)>i]，此时 mex(s)>i 相当于 0,…,i 在 s 中均出现过。
本题的 −1 个数不超过 300，所以每个替换方案至多只能填补 300 个空位。
考虑先预处理一个 dp 数组 f(i,j) 表示：有多少个长度为 i 值域在 [0,n] 且数值 0,…,j−1 均出现过的数组。我们将必须出现的数值 0,…,j−1 称为关键数字，这 j 个关键数字具体的数值其实我们并不关心，因为这 n+1 个数字的地位是等价的。
初态：f(i,0)=(n+1)i。
转移方程：分最后一位是否填关键数字，有两种转移
f(i,j)=f(i−1,j)×(n+1−j)+f(i−1,j−1)×j
这里的第二种转移是“最后一位填关键数字”，那么其他的 j−1 个关键数字必须出现，由于关键数字的具体取值不影响计数，这和 f(i−1,j−1) 的定义是一样的（双射）。
回到统计答案。对于当前前缀，设其中有 b 个 −1，设从小到大第 i 个空位的数值为 xi。那么一旦填上前 i 个空位，可以使得所有 xi≤v<xi+1 都有 mex(s)>v。则当前前缀的答案为
x1×f(b,0)+j=1∑b(xj+1−xj)×f(b,j)
设 W 表示 −1 的个数，时间复杂度 O(nW+W2)。
（因为本题只能提交 Kotlin，就叫 ChatGPT 帮我仿写了一份 Kotlin 2.2.0 的代码）
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
| import java.io.BufferedInputStream
typealias i64 = Long
const val mod = 998244353
fun qpow(a0: Int, b0: Int, p: Int): Int {
var a = a0
var b = b0
var ans = 1
while (b != 0) {
if (b and 1 != 0) {
ans = (1L * ans * a % p).toInt()
}
a = (1L * a * a % p).toInt()
b = b shr 1
}
return ans
}
const val W = 301
val f = Array(W + 1) { IntArray(W + 1) }
const val N = 200100
var n = 0
val a = IntArray(N)
val fa = IntArray(N)
fun get(x0: Int): Int {
var x = x0
var rt = x
while (fa[rt] != rt) {
rt = fa[rt]
}
while (fa[x] != x) {
val y = fa[x]
fa[x] = rt
x = y
}
return rt
}
var b = 0
fun ask(): Int {
var x = get(0)
var ans = (1L * x * f[b][0] % mod).toInt()
var i = 1
x = 0
var y: Int
while (i <= b) {
x = get(x)
y = get(x + 1)
ans = (
ans + 1L * (y - x) * f[b][i] % mod
).toInt()
if (ans >= mod) {
ans -= mod
}
i++
x++
}
return ans
}
fun main() {
val input = FastScanner()
n = input.nextInt()
for (i in 1..n) {
a[i] = input.nextInt()
}
for (i in 0..n + 1) {
fa[i] = i
}
val w = minOf(n, W)
f[0][0] = 1
for (i in 1..w) {
f[i][0] = qpow(n + 1, i, mod)
for (j in 1..w) {
f[i][j] = (
(
1L * (n + 1 - j) * f[i - 1][j] +
1L * j * f[i - 1][j - 1]
) % mod
).toInt()
}
}
val output = StringBuilder()
for (i in 1..n) {
if (a[i] == -1) {
b++
} else {
if (fa[a[i]] == a[i]) {
fa[a[i]] = a[i] + 1
}
}
output.append(ask())
output.append(if (i == n) '\n' else ' ')
}
print(output)
}
class FastScanner {
private val input = BufferedInputStream(System.`in`)
private val buffer = ByteArray(1 shl 16)
private var len = 0
private var ptr = 0
private fun read(): Int {
if (ptr >= len) {
len = input.read(buffer)
ptr = 0
if (len <= 0) {
return -1
}
}
return buffer[ptr++].toInt()
}
fun nextInt(): Int {
var c = read()
while (c <= 32 && c != -1) {
c = read()
}
var sign = 1
if (c == '-'.code) {
sign = -1
c = read()
}
var x = 0
while (c > 32 && c != -1) {
x = x * 10 + c - '0'.code
c = read()
}
return x * sign
}
}
|