結果

問題 No.1963 Subset Mex
コンテスト
ユーザー vjudge1
提出日時 2025-12-23 16:01:08
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 6 ms / 4,000 ms
コード長 1,775 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,543 ms
コンパイル使用メモリ 280,344 KB
実行使用メモリ 8,624 KB
最終ジャッジ日時 2025-12-23 16:01:13
合計ジャッジ時間 4,115 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,xn=105,xd=120;
int T,s,a[xn],d,b[xd],dp[xd][xn][xn],ans,pd[xd][xn];
template<typename T>inline void read(T &n){
	T w=1;n=0;char ch=getchar();
	while(!isdigit(ch)&&ch!=EOF){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)&&ch!=EOF)n=(n<<1)+(n<<3)+(ch&15),ch=getchar();
	n*=w;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	T=1;
	while(T--){
		read(s),d=0;for(int g=1;g<=s;g++)read(a[g]),d=max(d,a[g]);d+=10;
		for(int g=0;g<=d;g++)b[g]=0;for(int g=1;g<=s;g++)b[a[g]]++;
		for(int g=0;g<=d+1;g++)for(int h=0;h<=s;h++)for(int j=0;j<=s;j++)dp[g][h][j]=0;dp[d+1][0][0]=1;
		for(int g=d;g;g--)for(int h=0;h*(g+1)<=s;h++)for(int j=0;j<=s;j++)if(dp[g+1][h][j])
			for(int v=0;v+h<=b[g]||(v+2*h-b[g])*g<=s-b[g];v++){
				int e=max(h,v+2*h-b[g]),r=j+max(b[g]-v-h,0);
				dp[g][e][r]=(dp[g][e][r]+dp[g+1][h][j])%mod;
			}
		ans=0;
		for(int h=0;h<=s;h++)for(int j=0;j<=s;j++)if(dp[1][h][j]&&j+b[0]>=h){
			int e=j+b[0]-h;ans=(ans+1ll*(e+1)*dp[1][h][j])%mod;
		}
		for(int g=0;g<=d+1;g++)for(int h=0;h<=s;h++)pd[g][h]=0;pd[d+1][0]=1;int ki=0;
		for(int g=d;g>=0;g--){
			for(int h=ki;h>=0;h--)for(int j=0;j<=b[g];j++)pd[g][h+j]=(pd[g][h+j]+pd[g+1][h])%mod;
			ki+=b[g];
		}
		int kp=0,kl=b[0];
		for(int g=1;g<=d;g++){
			if(b[g]){
				int kk=0;int lo=1,lp=0;bool t=1;
				for(int h=g-1;h;h--){
					lp+=max(0,b[h]-lo);
					lo=max(lo,lo+lo-b[h]);
					if(lo>=10*s){t=0;break;}
				}
				if(t){
				lp+=b[0];
				int e=s-kl+1+lp-lo;
				for(int h=0;h<=min(e,s);h++)kk=(1ll*kk+pd[g][h]+mod-pd[g+1][h])%mod;kp=(kp+kk)%mod;
				}
			}
			kl+=b[g];
		}
		int ko=1;for(int g=1;g<=d;g++)ko=1ll*ko*(b[g]+1)%mod;
		if(!b[0]&&!b[1])kp=(kp+1)%mod;ans=(1ll*ans+kp+mod-ko)%mod;
		cout<<ans<<'\n';
	}
	return 0;
}
0