結果
問題 | No.1963 Subset Mex |
ユーザー |
|
提出日時 | 2022-07-02 09:07:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 936 bytes |
コンパイル時間 | 1,661 ms |
コンパイル使用メモリ | 167,380 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-11-26 22:35:58 |
合計ジャッジ時間 | 3,061 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 18 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int N=1e2;const int mod=998244353;void inc(int &x,int y){ if((x+=y)>=mod) x-=mod; }int n;int f[N+5][N+5][N+5];int c[N+5],mn=N+1;int g[N+5];int use(int x){if(!x) return 0;int s=0;g[x-1]=1;for(int i=x-1;i;i--){if(c[i]>=g[i]) s+=c[i]-g[i];g[i-1]=max(g[i],2*g[i]-c[i]);}return g[0]-c[0]-s;}int main(){scanf("%d",&n);for(int i=1,x;i<=n;i++){scanf("%d",&x);if(x==1) x=0;c[x]++; mn=min(mn,x);}int ans=0;f[N+1][0][0]=1;for(int i=N;i>=0;i--){int tu=use(i);for(int j=0;j*(i+1)<=n;j++)for(int k=0;k<=n;k++){if(!f[i+1][j][k]) continue;for(int t=0;t<=n;t++){int tj=max(j,j*2+t-c[i]),tk=k+max(0,c[i]-j-t);if(!i&&tj>0&&c[i]+k>=j+t) inc(ans,f[i+1][j][k]);if((i!=mn||tk>0)&&!tj&&t>0&&tk+1>=tu) inc(ans,f[i+1][j][k]);if(i) inc(f[i][tj][tk],f[i+1][j][k]);}}}printf("%d\n",(ans+1)%mod);return 0;}