結果
問題 | No.2522 Fall in love, Girls! |
ユーザー |
![]() |
提出日時 | 2023-10-27 23:00:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,006 ms / 2,000 ms |
コード長 | 2,198 bytes |
コンパイル時間 | 4,945 ms |
コンパイル使用メモリ | 263,124 KB |
最終ジャッジ日時 | 2025-02-17 15:45:18 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 struct combi{ deque<mint> kaijou; deque<mint> kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(kaijou[i-1]*i); } mint b=kaijou[n].inv(); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(kaijou_[0]*k); } } mint combination(int n,int r){ if(r>n)return 0; mint a = kaijou[n]*kaijou_[r]; a *= kaijou_[n-r]; return a; } mint junretsu(int a,int b){ mint x = kaijou_[a]*kaijou_[b]; x *= kaijou[a+b]; return x; } mint catalan(int n){ return combination(2*n,n)/(n+1); } }; combi C(2500000); int main(){ int N,M,K; cin>>N>>M>>K; dsu D(N); vector<vector<int>> E(N); vector<int> a(K),b(K); rep(i,K){ cin>>a[i]>>b[i]; a[i]--,b[i]--; D.merge(a[i],b[i]); E[a[i]].push_back(b[i]); } rep(i,N)sort(E[i].begin(),E[i].end()); int sum = 0; vector<mint> tdp(2,0); auto g = D.groups(); rep(i,g.size()){ sort(g[i].begin(),g[i].end()); vector<mint> dp(1<<g[i].size()); dp[0] = 1; mint X = 0,Y = 0; rep(j,(1<<g[i].size())-1){ rep(k,g[i].size()){ if((j>>k)&1)continue; bool f = true; rep(l,g[i].size()){ if((j>>l)&1){ if(binary_search(E[g[i][l]].begin(),E[g[i][l]].end(),g[i][k])){ f = false; break; } } } if(f){ if((j|(1<<k))+1==(1<<g[i].size())){ if(g[i][k]<M)X += dp[j]; else Y += dp[j]; } dp[j|(1<<k)] += dp[j]; } } } //cout<<X.val()<<' '<<Y.val()<<endl; if(sum==0){ tdp[0] = X; tdp[1] = Y; } else{ mint t0 = 0,t1 = 0; t0 += C.combination(g[i].size()+sum-1,sum-1) * (X+Y) * tdp[0]; t1 += C.combination(g[i].size()+sum-1,sum-1) * (X+Y) * tdp[1]; t0 += C.combination(g[i].size()+sum-1,sum) * X * (tdp[0]+tdp[1]); t1 += C.combination(g[i].size()+sum-1,sum) * Y * (tdp[0]+tdp[1]); tdp[0] = t0; tdp[1] = t1; } sum += g[i].size(); } cout<<tdp[1].val()<<endl; return 0; }