/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ N の整数列 A と正整数 K が与えられます。
A に対して、以下の操作を何回でも行うことができます。
- A_i+A_{i+1} が K で割り切れるような 1 以上 N-1 以下の整数 i を選び、A_i と A_{i+1} を入れ替える。
操作を 0 回以上行った後の A としてあり得る数列の総数を 998244353 で割った余りを求めてください。
1 つの入力につき、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
1 つ目のテストケースでは、操作を 0 回以上行った後の A としてあり得る数列は (1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7) の 4 つです。
Score : 500 points
Problem Statement
You are given an integer sequence A of length N and a positive integer K.
You can perform the following operation on A any number of times:
- Choose an integer i with 1 \leq i \leq N-1 such that A_i + A_{i+1} is divisible by K, and swap A_i and A_{i+1}.
Find the total number, modulo 998244353, of distinct sequences that A can become after performing the operation zero or more times.
Solve T test cases per input.
Constraints
- 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
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case \mathrm{case}_t is given in the following format:
N K A_1 A_2 \dots A_N
Output
Output the answers over a total of T lines. The t-th line should contain the answer for the t-th test case.
Sample Input 1
3 4 3 1 2 4 7 6 4 1 5 3 6 2 4 3 2 2 2 3
Sample Output 1
4 6 1
For the first test case, the sequences that A can become after performing the operation zero or more times are these four: (1,2,4,7),(1,4,2,7),(1,4,7,2),(2,1,4,7).