ABC 401-500/ABC431F - Almost Sorted 2 - 競技プログラミング用 知識集積所

---

問題

ABC431F

必要知識

B以下レベルの内容は省略

• 順列組み合わせ※
• 二項係数※
• 剰余類環
  • 繰り返し二乗法※
• sliding window法

考え方

数学問題。

例えばD=2で{1,2,2,4}という数列の場合、以下の9つが答えである。

• {1,2,2,4}
• {1,2,4,2}
• {1,4,2,2}
• {2,1,2,4}
• {2,1,4,2}
• {2,2,1,4}
• {2,4,2,1}
• {4,2,1,2}
• {4,2,2,1}

これらは、以下の3つの数列のうち、1の直前以外の3か所に4を合計1つ入れることで作ることができる。

• {1,2,2}
• {2,1,2}
• {2,2,1}

そして、これらは、以下の数列の2ヶ所に2を合計2つ入れることで作ることができる。

• {1}

これらを逆再生して数列Bを生成することを考えれば、
この数列のパターン数はComb(3,2)*Comb(3,1)で求められる。

もっと複雑な配列でも同様に、Comb(i-d以上i以下の数の個数,iの個数)の総乗を取れば答えであることが証明できる。
よって、あとはこれをどう高速に計算するかだけである。

Aの中身は最大でも10^6程度なので、全ての整数について何回登場したかのカウントをすることは可能。
ということは、i-d以上i以下の数の個数はsliding window法で高速に求まる。
二項係数※は、事前にN以下の階乗を全て求めておけば、これもすぐに求まる。
よって、全体としても十分高速に処理できる。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法※のアルゴリズムも用意しておくこと。

解答例

解答例

注意点

別解