ABC 462 G — Completely Wrong

考察

位置iが完全に外れる事象 C_{P_i}≠G_i の全積を包除すると、選んだ一致位置は値class kごとの選択数D_kだけで数えられる。

採用する候補: 各値kの出現数 X_k,Y_kから多項式 f_k(x)=Σ_j(-1)^j C(X_k,j)C(Y_k,j)j!x^j を作り、全f_kをNTTで積み、係数c_iに(N-i)!を掛けて総和する。

class kでj位置を一致させる方法は両側からj個選びbijectionをj!通り作る数で、全class独立な畳み込みになり、残りN-i位置は(N-i)!通り自由に並べられる。

棄却する候補: 全N!順列を列挙し、どの位置でもC_{P_i}≠G_iか検査する。

factorial個の候補を扱えず、値ごとの対称性を利用していない。

包除subsetの符号は一致を強制した総位置数ΣD_kのparityだけで、多項式係数の(-1)^jへ分配できる。

各factor次数の総和はNなので、小次数factorからpriority queueで畳み込むと O(N log^2 N) に抑えられる。

C,Gの値frequency X,Yとfactorialを前計算する。各kでj=0..min(X_k,Y_k)の係数を作り、size順にNTT convolutionしてfを得る。ans=invFact[N]×Σ_i f_i×fact[N-i]をmodulus上で計算する。

典型の発動条件

包除原理のclass別生成関数

発動条件: permutationの位置一致禁止が値classごとに対称なとき。

各classの一致数選択を多項式にし、積で全配分を畳み込む。

多項式積のsmall-to-large convolution

発動条件: factor次数総和がNで多数factorを掛けたいとき。

小さい二factorからNTT mergeしてlog段を抑える。

問題固有の要素

permutation包除を位置subsetの2^Nで回さず、同値classごとの選択個数へorbit圧縮する。

別の問題へ持ち帰る視点: 独立class間の総選択数だけを追う式は、生成関数の積としてそのまま実装できる。

正当性

一致位置を指定する包除で、値kのj位置選択はC(Y_k,j)、それへ相異なるC側indexを割り当てる数は(X_k)_j。従ってfactorのj次係数は(−1)^j C(Y_k,j)(X_k)_j。積のi次係数は全一致指定i位置の交差項で、残り(N−i)!を掛けて合計すると完全不一致順列数。全N!で割るとその確率になる。

実装上の注意

  • 係数のj!を誤ってD_k!ではなく別箇所へ重複させない。最後にN!で割る確率正規化と負係数modを処理する。

復習の核

  • 一classでj個一致を強制する C(X,j)C(Y,j)j! のbijectionを数え、class積後の残り(N-i)!を導く。

計算量と制約

時間

O(N log²N)。値class包除多項式を小次数順NTTで合成する。

空間

O(N log N)の積木保持、逐次解放でO(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1\le N\le 2\times 10^5; 1\le C_i,G_k\le N; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Completely Wrong の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 包除・Möbius反転で重複を補正する

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

    主タグ: 集合上の包除原理

    補助タグ: 畳み込み・相互相関 生成関数による組合せ構造の符号化 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 包除・Möbius反転で重複を補正する

    • 条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。

    先に読む単元:

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

    • 選択順を二項係数だけで式化する数え上げ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題