はまやんはまやんはまやん

hamayanhamayan's blog

Russian Dolls Ways [CSAcademy #73 D]

https://csacademy.com/contest/round-73/task/russian-dolls-ways/

N個のマトリョーシカ人形がある。
i番目の人形のサイズはA[i]である。
サイズがA[i]<A[j]であればj番目の中にi番目の人形を入れられる。
複数入れ子もOK
適切に入れて最終的な人形を少なくしたい。
人形を最小化する入れ方の組み合わせ数は?

解法

まず最終的に何個にできるか考えてみよう。
これはサイズ毎に集計した時の個数の最大値となる。
ここまでは思いつくと思うが、ここからが発想を要求するので難しい。
 
最大個数のサイズをma_numでその個数をma_frqとする。
すると、ma_num以外のサイズの人形は必ず1つのma_numサイズの人形に属すことになる。
しかし、マトリョーシカ状態を保つために、同じサイズの人形は同時に属せない。
そのため、求めたい組み合わせ数というのは「ma_num以外のサイズの人形をma_numサイズの人形に割り当て、かつ、同じサイズの人形が属さないような組合せ数」
これは各サイズ毎に割り当てる組合せを考えていけばいい。
具体的にはあるサイズの個数がc個であれば、

  • ma_numサイズの人形の選び方 C(ma_frq, c)
  • どのma_numサイズの人形に、あるサイズの人形を割り当てるかの並べ方 c!

となるので「c! * C(ma_frq, c)」を掛け合わせて答える。

int N;
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    map<int, int> cnt;
    rep(i, 0, N) {
        int x; cin >> x;
        cnt[x]++;
    }

    int ma_num, ma_frq = -1;
    fore(p, cnt) if (ma_frq < p.second) {
        ma_num = p.first;
        ma_frq = p.second;
    }

    mint ans = 1;
    fore(p, cnt) if (p.first != ma_num) ans *= com.fac[p.second] * com.aCb(ma_frq, p.second);
    cout << ans << endl;
}