← 返回题目列表

AtCoder · arc223_b

B. K-整除交换的有效数组

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

分数: 500 点

问题陈述

给你一个整数序列 A 长度 N 和一个正整数 K.
您可以对 A 任意次数:

  • 选择一个整数 i 与 1 \leq i \leq N-1 这样 A_i + A_{i+1} 可以除以 K,并交换 A_i 和 A_{i+1}.

求总数,取模 998244353,不同的序列 A 可以在执行操作零次或多次后变为。

解决 T 每个输入的测试用例。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例 \mathrm{case}_t 按以下格式给出:

N K  
A_1 A_2 \dots A_N  

输出

输出总共的答案 T 行。 的 t- 第行应包含以下问题的答案 t- 第一个测试用例。


示例输入 1

3
4 3
1 2 4 7
6 4
1 5 3 6 2 4
3 2
2 2 3

示例输出 1

4
6
1

对于第一个测试用例,序列 A 执行操作零次或多次后可以变成以下四种: (1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7).