← 返回题目列表

Codeforces · 2226/G

G. 停止点

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

给定一个数组 $$$a$$$,大小为 $$$n$$$ ($$$1 \leq a_i \leq m$$$)。

考虑数组 $$$[1, 2, \ldots, m]$$$ 的所有 $$$m!$$$ 排列。对于任何排列 $$$p$$$,将数组 $$$b_p$$$ 定义为通过连接数组 $$$a$$$ 和排列 $$$p$$$ 形成的数组。更正式地说,$$$b_p = [a_1, a_2, \ldots, a_n, p_1, p_2, \ldots, p_m]$$$。

设 $$$f(i)$$$ 表示排列 $$$p$$$ 的数量,使得数组 $$$b_p$$$ 恰好包含 $$$i$$$ 回文 $$$^{\text{*}}$$$ 的子数组 偶数长度.

您的任务是计算 $$\sum_{i=0}^{10^{100}} f(i)^{i+1}.$$

由于答案可能很大,因此应该以 $$$998\,244\,353$$$ 为模进行计算。

$$$^{\text{*}}$$$数组 $$$[c_1, c_2, \ldots, c_k]$$$ 被认为是回文数组,如果 $$$c_i = c_{k+1-i}$$$ 对于所有 $$$1 \le i \le k$$$ 来说是回文数组。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 10^6$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — 数组的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,在新行上打印一个整数 - $$$\sum_{i=0}^{10^{100}} f(i)^{i+1}$$$ 模 $$$998\,244\,353$$$。

示例

输入
复制

5
4 3
3 1 2 1
1 1
1
9 4
4 1 2 1 3 3 1 2 1
6 3
1 1 3 1 1 1
10 6
4 4 1 2 1 3 3 1 2 1

输出
复制

6
1
1248960
258
14006753

注意

在第一个测试用例中,$$$n=4$$$、$$$m=3$$$ 和 $$$a=[3,1,2,1]$$$。

让我们列出所有排列并计算偶数长度的回文子数组的数量:

  • $$$p_1 = [1, 2, 3]$$$, $$$b_{p_1} = [3, 1, 2, 1, 1, 2, 3]$$$,偶数长度的回文子数组的数量为$$$2$$$。
  • $$$p_2 = [1, 3, 2]$$$, $$$b_{p_2} = [3, 1, 2, 1, 1, 3, 2]$$$,偶数长度的回文子数组的数量为 $$$1$$$。
  • $$$p_3 = [2, 1, 3]$$$, $$$b_{p_3} = [3, 1, 2, 1, 2, 1, 3]$$$,偶数长度的回文子数组的数量为$$$0$$$。
  • $$$p_4 = [2, 3, 1]$$$, $$$b_{p_4} = [3, 1, 2, 1, 2, 3, 1]$$$,偶数长度的回文子数组的数量为$$$0$$$。
  • $$$p_5 = [3, 1, 2]$$$, $$$b_{p_5} = [3, 1, 2, 1, 3, 1, 2]$$$,偶数长度的回文子数组的数量为$$$0$$$。
  • $$$p_6 = [3, 2, 1]$$$, $$$b_{p_6} = [3, 1, 2, 1, 3, 2, 1]$$$,偶数长度的回文子数组的数量为$$$0$$$。

因此,对于所有 $$$i \gt 2$$$,我们有 $$$f(0) = 4$$$、$$$f(1) = 1$$$、$$$f(2) = 1$$$ 和 $$$f(i) = 0$$$。因此,答案是$$$4^1 + 1^2 + 1^3 = 6$$$。