Codeforces #1064 : Div1 B. Marble Council

割と良い結果だった回。
https://codeforces.com/contest/2165/problem/B

問題

整数のmultisetが与えられる。
これをいくつかのmultisetに分割し、それぞれから最頻値のうち１つを抽出してまとめたmultisetを考える。
こうして構築できるmultisetは何通りか。

解法

入力中にある整数がc個ある場合、最終的なmultisetに何個現れるかを考える。
1～c個置くようにmultisetに分割するのは楽である。
問題は0個現れるようにすることで、これは表に現れる整数群に対し、その個数の総和以下ならその整数を隠しきることができる。

dp(n,m) := 整数の頻度の小さい順にn種目まで考えたとき、表に現れる整数群における頻度の総和がmであるような、最終的なmultisetの個数
として、順に埋めて行こう。

int T,N,A[5050];
const ll mo=998244353;
int C[5050];
int D[5050];

ll dp[5050];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+2) C[i]=0;
		FOR(i,N) {
			cin>>x;
			C[x-1]++;
		}
		vector<int> D;
		FOR(i,N) if(C[i]) D.push_back(C[i]);
		ZERO(dp);
		dp[0]=1;
		sort(ALL(D));
		ll ret=0;
		FOR(i,D.size()) {
			//take
			int v=D[i];
			for(j=N;j>=v;j--) {
				(dp[j]+=dp[j-v]*v)%=mo;
				if(i==D.size()-1||j>=D.back()) (ret+=dp[j-v]*v)%=mo;
			}
		}
		cout<<ret<<endl;
		
		
	}
}

まとめ

ちょっと手間取ったけど、無事解けて良かったね。