ARC223 B - Valid Arrays by K-Divisible Swaps

考え方

数列を、以下のようにグループにわける。

• $k$ で割った余りが $0$ であるものが連続する部分
• $k$ で割った余りが $1$ または $k-1$ であるものが連続する部分
• $k$ で割った余りが $2$ または $k-2$ であるものが連続する部分
• （略）
• $k$ で割った余りが $k/2$ であるものが連続する部分（kが偶数の場合のみ）

入れ替えの条件について考える。
まず、異なるグループ間での交換は不可能、よってグループ分けが崩れることはない。
そして、同じグループ間で入れ替えた場合、これもグループ分けが崩れることはない。
したがって、各グループ内で独立に考えて差し支えない。
グループ内の並べ替え方を順に考え、全てかけ合わせれば答え。

まず、$k$ で割った余りが $0$ であるグループ、または $k/2$ であるグループ。
この場合、グループ内の任意の $2$ つが入れ替え可能で、つまり最終的に任意の順に並べられる。
つまり、見分けがつかないものを含む順列の公式 $\dfrac{n!}{p!q!r!\dots}$ で求まる。

次に、$k$ で割った余りが $i$ または $k-i$ であるグループ。
この場合、余りが $i$ であるものと $k-i$ であるものは、入れ替え可能。
しかし、$i$ であるもの同士や $k-i$ であるもの同士は、入れ替え不可能。
最終的には、$i$ であるものの順番は保持、$k-i$ であるものの順番も保持した任意の順列にできる。
つまり、$i$ であるものの位置の選び方を選べばよく、二項係数として求まる。

前述のとおり、グループごとの値を全てかけあわせて $998244353$ で割った余りが答え。

計算量は、1ケース当たり $O(N\log N)$ である。

入力例1での動作

$2$ つ目のテストケースのみ考える。

入力を受け取る。

n: 6
k: 4
a: {1, 5, 3, 6, 2, 4}

各要素を $4$ で割った余りは、次のようになる。

a mod 4: {1, 1, 3, 2, 2, 0}

これを参考に、連続するグループへ分ける。

{1, 5, 3}
{6, 2}
{4}

各グループの並べ替え方を求める。

まず、$\{1,5,3\}$ のグループを考える。
$4$ で割った余りが $1$ のものは $2$ 個、余りが $3$ のものは $1$ 個である。
それぞれの余りの中で元の順番は変わらないため、余りが $1$ のものを置く $2$ 位置を選べばよい。
よって、${}_3\mathrm{C}_2=3$ 通りである。

次に、$\{6,2\}$ のグループを考える。
どちらも余りが $2=k/2$ なので、この範囲内を任意の順に並べられる。
よって、$\dfrac{2!}{1!1!}=2$ 通りである。

最後に、$\{4\}$ のグループを考える。
余りが $0$ なので、この範囲内を任意の順に並べられる。
よって、$\dfrac{1!}{1!}=1$ 通りである。

以上をかけ合わせると $3\times2\times1=6$ となる。
したがって、答えは $6$ である。

注意点

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
順列数や二項係数を何度も使うため、階乗と階乗の逆元を前計算しておく。

別解

特になし。