CSAcademy Round #73 : D. Russian Dolls Ways

Div2とはいえ、いつもよりは楽な回。
https://csacademy.com/contest/round-73/task/russian-dolls-ways/

問題

ロシア人形がN個あり、それぞれ大きさが与えられる。
異なる大きさの人形は入れ子にできる。
人形を可能な限り入れ子にし、外に見える個数を最小にしたい。
その際入れ子の仕方の組み合わせは何通りあるか。

解法

異なる大きさの人形同士はいくらでも入れ子にできるので、最小の個数とは結局同じ大きさの人形の個数の最大値である。
S(k)をサイズkの人形の個数とする。
個数が最大となるサイズを1個求め、それをmとしよう。
サイズmの人形S(m)個を固定すると、他のサイズの人形はそのどれを入れ子にするか、もしくはどれに入れ子にされるかを考えればよい。

よってm以外のサイズkに対しP(m,S(k))の積を取ればよい。

int N;
map<int,int> M;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll mo=1000000007;
ll perm(ll N_, ll C_) {
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		M[-x]++;
	}
	
	int ma=0;
	FORR(m,M) ma=max(ma,m.second);
	
	ll ret=1;
	int skip=1;
	FORR(m,M) {
		if(m.second==ma && skip) {
			skip=0;
			continue;
		}
		ret=ret*perm(ma,m.second)%mo;
	}
	cout<<ret<<endl;
	
}

まとめ

前々回も入れ子問題だったな。