Codeforces #831 : F. Conditional Mix

こういうのサクっとかけないな…。
https://codeforces.com/contest/1740/problem/F

問題

N要素の整数列Aが与えられる。
初期状態で、{A[i]}からなるN個の整数集合があったとする。
共通部分を持たない2つの集合を、和集合で置き換える作業を任意回数行えるとする。

最終的な整数集合の集合について、それぞれ整数集合の個数を置き換えたmultisetとして構築できるのは何通りか。

解法

最終的な整数集合のサイズを降順に並べた数列をMとする。
また、Aにおけるxの頻度をC[x]とする。

Mの総和は明らかにN。
また、1つの整数集合に同じ数値は2つ存在できないことから、Mのk要素のprefixに対しその和はmin(k,C[i])以下でなければならない。
これを数え上げて行こう。
Mのサイズの小さい順に、同じサイズの整数集合が何個取れるかをDPで数えて行く。

int N;
int A[2020];
int S[2020];
const ll mo=998244353;
vector<int> V;

ll dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A[x-1]++;
	}
	
	FOR(i,N) for(j=1;j<=N;j++) S[j]+=min(j,A[i]);
	
	dp[0][0]=1;
	for(i=N;i>=1;i--) {
		for(x=N;x>=0;x--) {
			ll a=0;
			for(k=0;x+k*i<=N;k++) {
				if(x-k>=0) {
					if(N-x<=S[i]) (a+=dp[x][k])%=mo;
					dp[x][k]=0;
				}
				(dp[x+k][k]+=a)%=mo;
				if(N-(x+k)>S[i-1]) dp[x+k][k]=0;
			}
		}
	}
	ll ret=0;
	FOR(i,N+1) ret+=dp[N][i];
	cout<<ret%mo<<endl;
	
	
}

まとめ

こういうのサクっと解けるといいんだけどな。