L3-027 可怜的复杂度

Statement

Metadata

作者: 吉如一
单位: 北京大学
代码长度限制: 16 KB
时间限制: 8000 ms
内存限制: 256 MB

可怜有一个数组 $A$ ，定义它的复杂度 $c(A)$ 等于它本质不同的子区间个数。举例来说， $c([1,1,1]) = 3$ ，因为 $[1,1,1]$ 只有 $3$ 个本质不同的子区间 $[1]$ 、 $[1,1]$ 和 $[1,1,1]$ ；而 $c([1,2,1]) = 5$ ，它包含 $5$ 个本质不同的子区间 $[1]$ 、 $[2]$ 、 $[1,2]$ 、 $[2,1]$ 、 $[1,2,1]$ 。

可怜打算出一道和复杂度相关的题目。众所周知，引入随机性往往可以让一个简单的题目脱胎换骨。现在，可怜手上有一个长度为 $n$ 的正整数数组 $x$ 和一个正整数 $m$ 。接着，可怜会独立地随机产生 $n$ 个 $[1,m]$ 中的随机整数 $y_i$ ，并把 $x_i$ 修改为 $mx_i+y_i$ 。

显然，一共有 $N=m^n$ 种可能的结果数组。现在，可怜想让你求出这 $N$ 个数组的复杂度的和。

输入格式

第一行给出一个整数 $t$ ( $1 \le t \le 5$ ) 表示数据组数。

对于每组数据，第一行输入两个整数 $n$ 和 $m$ ( $1 \le n \le 100, 1 \le m \le 10^9$ )，第二行是 $n$ 个空格隔开的整数表示数组 $x$ 的初始值 ( $1 \le x_i \le 10^9$ )。

输出格式

对于每组数据，输出一行一个整数表示答案。答案可能很大，你只需要输出对 $998244353$ 取模后的结果。

输入样例

4
3 2
1 1 1
3 2
1 2 1
5 2
1 2 1 2 1
10 2
80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045

输出样例

Last update: May 4, 2022