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