結果
問題 | No.2669 Generalized Hitting Set |
ユーザー | kotatsugame |
提出日時 | 2024-03-08 22:38:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,277 ms / 4,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 744 ms |
コンパイル使用メモリ | 70,064 KB |
実行使用メモリ | 136,132 KB |
最終ジャッジ日時 | 2024-09-29 20:06:45 |
合計ジャッジ時間 | 16,550 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include<iostream>#include<cassert>#include<atcoder/modint>using namespace std;using mint=atcoder::static_modint<999000061>;int N,M,K;int cnt[1<<24];mint now[1<<24];mint comb[25][25],coef[25][25],c[25];int ans[3<<17];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>M>>K;for(int i=0;i<M;i++){string s;cin>>s;int S=0;for(int j=0;j<N;j++)if(s[j]=='1')S|=1<<j;cnt[S]++;}for(int k=0;k<N;k++)for(int i=0;i<1<<N;i++)if(i>>k&1)cnt[i^1<<k]+=cnt[i];for(int i=0;i<=N;i++){comb[i][0]=comb[i][i]=1;for(int j=1;j<i;j++)comb[i][j]=comb[i-1][j-1]+comb[i-1][j];}for(int k=K;k<=N;k++)coef[k][k]=1;for(int k=N-1;k>=K;k--){for(int i=k+1;i<=N;i++){for(int j=1;j<=N;j++)coef[k][j]-=coef[i][j]*comb[i][k];}}for(int k=K;k<=N;k++){c[k]=0;for(int i=k;i>=K;i--)c[k]+=coef[i][k];}for(int i=0;i<1<<N;i++){int pc=__builtin_popcount(i);now[i]=mint::raw(cnt[i])*c[pc];}for(int k=0;k<N;k++)for(int i=0;i<1<<N;i++)if(i>>k&1)now[i]+=now[i^1<<k];for(int i=0;i<=M;i++)ans[i]=1e9;for(int i=0;i<1<<N;i++){int t=now[i].val();assert(0<=t&&t<=M);ans[t]=min(ans[t],__builtin_popcount(i));}for(int i=M;i>=1;i--)ans[i-1]=min(ans[i-1],ans[i]);for(int i=1;i<=M;i++)cout<<ans[i]<<"\n";}