結果
問題 | 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 4000000000000000001struct 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;}