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での動作

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

入力を受け取る。

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

a を仮に全て $4$ で割った余りすると、以下のようになる。

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

これを参考に a をグループに分ける。
$k=4$ なので、以下に分ける。

• $0$ が連続する部分
• $1$ と $3$ が連続する部分
• $2$ が連続する部分

a': { {1,5,3}, {6,2}, {4} }

各部分の並べ替えのパターン数を求めていく。

まず、$\{1,5,3\}$ 部分。
$4$ で割った余りが異なるもの同士は入れ替えられるが、同じものは入れ替えられない。
よって余りが $1$ のもの $2$ つを何番目に置くかを考えればよく、${}_3\mathrm{C}_2 = 3$ 通り。

次に、$\{6,2\}$ 部分。
この範囲内を任意の順に並べられる。
よって見分けがつかないものを含む順列で考えて、$\dfrac{2!}{1!1!} = 2$ 通り。

最後に、$\{4\}$ 部分。
この範囲内を任意の順に並べられる。
よって見分けがつかないものを含む順列で考えて、$\dfrac{1!}{1!} = 1$ 通り。

これらをすべてかけて $3 \times 2 \times 1 = 6$ を $998244353$ で割った余りが答え。

注意点

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

別解

特になし。