ABC 226 F — Score of Permutations

考察

順列を矢印 i→p_i で描くと互いに素な巡回へ分解され、全てのボールが戻る時刻は巡回長の最小公倍数になる。誰が各巡回に属するかはスコアへ影響しない。

採用する候補: Nの整数分割として巡回長の多重集合を列挙し、そのcycle typeを持つ順列数と巡回長LCMのK乗の積を加算する。

N=50ではN!個の順列は扱えないが整数分割数は十分小さく、同じ巡回長頻度を持つ順列を一状態へ同一視できる。

棄却する候補: 全順列を生成し、ボールが戻るまで操作をシミュレーションする。

順列数N!が支配的で、各順列の周期を高速に求めてもN=50には全く届かない。

長さlの巡回がf_l個あるcycle typeの順列数は N!/Π_l(l^(f_l)·f_l!) であり、頂点の分割順と各巡回の回転同値をまとめて除いている。

同じcycle typeではスコアが lcm({l | f_l>0}) に等しいため、個々の順列を復元せず頻度とLCMだけで全寄与を計算できる。

非減少な巡回長を選ぶDFSで総和Nの整数分割を列挙し、各頻度の順列数を階乗・逆元で求め、count×lcm^Kを998244353で加算する。

典型の発動条件

順列の巡回分解

発動条件: 順列を同時に繰り返し適用し、元へ戻る周期や不変な軌道が評価に現れるとき。

各軌道を巡回置換として分解し、全体周期を巡回長のLCMとして求める。

cycle typeの整数分割列挙

発動条件: 順列の評価が各要素の名前でなく巡回長の多重集合だけに依存し、Nが50程度のとき。

Nの整数分割を列挙し、同じ巡回構造の順列を組合せ係数でまとめて数える。

問題固有の要素

ボールの所有者という属人的な状態を捨て、巡回長だけを残すと、N!個の過程がNの整数分割個へ圧縮される。

別の問題へ持ち帰る視点: 置換過程の総和では、評価が共役類すなわちcycle typeだけで決まらないかを確認し、ラベル付き対象を型別にまとめる。

正当性

順列の全体周期は巡回長のLCM。頻度f_lのcycle typeの個数はN!/Π(l^{f_l}f_l!)で、巡回回転と同長巡回の交換を除いている。非減少な巡回長のDFSは全typeを一度列挙するので、その個数にLCM^Kを掛けた和が全順列のスコア和になる。

実装上の注意

  • 同じ長さの巡回のf!と各巡回の回転lを両方除く。LCM更新とK乗は整数値とmod値を混同せず、整数分割を重複なく列挙する。

復習の核

  • 順列を繰り返す問題では、まず矢印を描いて巡回長を出し、答えが要素名を忘れてcycle typeだけで決まるかを見る。

計算量と制約

時間

O(Π(N)(N log N+log K))を上界とする。Π(N)は整数分割数。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 50; 1 \leq K \leq 10^4; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Score of Permutations の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 組合せ係数と対称性で数える

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 組合せ係数・数え上げ

    補助タグ: 有界全列挙・有限case分解 法上の四則演算・高速累乗・逆元

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 組合せ係数と対称性で数える

    • 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。

    先に読む単元:

    この解説で扱わないこと:

    • 重なりを交互加減する包除・Möbius反転。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題