結果
問題 | No.2522 Fall in love, Girls! |
ユーザー |
![]() |
提出日時 | 2023-10-27 22:09:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 849 ms / 2,000 ms |
コード長 | 1,815 bytes |
コンパイル時間 | 2,490 ms |
コンパイル使用メモリ | 204,324 KB |
最終ジャッジ日時 | 2025-02-17 15:07:47 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;int main(){int N, M, K;cin >> N >> M >> K;vector<int> X(K), Y(K);for (int i = 0; i < K; i++){cin >> X[i] >> Y[i];X[i]--;Y[i]--;}vector<int> idx;for (int i = 0; i < K; i++){idx.push_back(X[i]);idx.push_back(Y[i]);}sort(idx.begin(), idx.end());idx.erase(unique(idx.begin(), idx.end()), idx.end());if (idx.empty()){idx.push_back(0);}int cnt = idx.size();vector<int> X2(K), Y2(K);for (int i = 0; i < K; i++){X2[i] = lower_bound(idx.begin(), idx.end(), X[i]) - idx.begin();Y2[i] = lower_bound(idx.begin(), idx.end(), Y[i]) - idx.begin();}vector<int> p(cnt, 0);for (int i = 0; i < K; i++){p[Y2[i]] |= 1 << X2[i];}vector<long long> a(cnt, 0);for (int i = 0; i < cnt; i++){if (p[i] == 0){vector<long long> dp(1 << cnt, 0);dp[1 << i] = 1;for (int j = 0; j < (1 << cnt); j++){for (int k = 0; k < cnt; k++){if ((j >> k & 1) == 0 && (j & p[k]) == p[k]){int j2 = j | (1 << k);dp[j2] += dp[j];dp[j2] %= MOD;}}}a[i] = dp[(1 << cnt) - 1];}}vector<int> idx2(N, -1);for (int i = 0; i < cnt; i++){idx2[idx[i]] = i;}long long sum = 0;for (int i = 0; i < cnt; i++){sum += a[i];}sum %= MOD;long long ans = 0;long long tmp1 = 1;for (int i = cnt + 1; i < N; i++){tmp1 *= i;tmp1 %= MOD;}long long tmp2 = 1;for (int i = cnt; i < N; i++){tmp2 *= i;tmp2 %= MOD;}for (int i = M; i < N; i++){if (idx2[i] == -1){ans += sum * tmp1;ans %= MOD;} else {ans += a[idx2[i]] * tmp2;ans %= MOD;}}cout << ans << endl;}