← 返回题目列表

AtCoder · arc187_b

B. CC 总和

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

对于序列 A = (A_1, \ldots, A_N) 长度 N,定义 f(A) 如下。

  • 准备一个图表 N 顶点标记 1 to N 和零边缘。对于每个整数对 (i, j) 满意 1 \leq i < j \leq N,如果 A_i \leq A_j,绘制连接顶点的双向边 i 和 j。定义 f(A) 作为结果图中连接分量的数量。

给你一个序列 B = (B_1, \ldots, B_N) 长度 N。的每个元素 B is -1 或之间的整数 1 和 M,包括在内。

通过替换每次出现的 -1 in B 之间的整数 1 和 M,可以获得 M^q 序列 B',其中 q 是数量 -1 in B.

求总和,模 998244353,属于 f(B') 总体而言 B'.

约束

  • 所有输入数字均为整数。
  • 2 \leq N \leq 2000
  • 1 \leq M \leq 2000
  • 每个 B_i is -1 或之间的整数 1 和 M,包括在内。

输入

输入由标准输入按以下格式给出:

N M
B_1 \ldots B_N

输出

打印答案。


示例输入 1

3 3
2 -1 1

示例输出 1

6

存在三种可能的序列 B': (2,1,1), (2,2,1),和 (2,3,1).

当 B' = (2,1,1),仅在顶点之间绘制边 2 和 3,因此连接组件的数量为 2。因此, f(B') = 2.

同样, f(B') = 2 为 B' = (2,2,1) 和 f(B') = 2 为 B' = (2,3,1),所以答案是 2 + 2 + 2 = 6.


示例输入 2

10 8
-1 7 -1 -1 -1 2 -1 1 -1 2

示例输出 2

329785

示例输入 3

11 12
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

示例输出 3

529513150

记得求模求和 998244353.