結果
問題 |
No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
|
ユーザー |
![]() |
提出日時 | 2022-12-05 02:13:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 1,000 ms |
コード長 | 1,312 bytes |
コンパイル時間 | 699 ms |
コンパイル使用メモリ | 73,692 KB |
最終ジャッジ日時 | 2025-02-09 05:18:32 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; int main(){ vector<ll> L(19); vector<ll> A(19, 0); for (ll i = 0; i < 19; i++){ cin >> L[i]; for (ll j = 0; j < L[i]; j++){ ll a; cin >> a; A[i] += (1LL << (a - 1)); } } /*for (ll i = 0; i < 19; i++){ cout << A[i] << " "; } cout << endl;*/ vector<ll> dp1((1 << 19), 0);//奇数 vector<ll> dp2((1 << 19), 0);//偶数 dp2[0] = 1; for (ll i = 0; i < (1 << 19) - 1; i++){ ll popcnt1 = __builtin_popcount(i); for (ll j = 0; j < 19; j++){ if ((i >> j) & 1){ continue; } if ((A[j] >> popcnt1) & 1){ ll bitmask = (1 << (j + 1)) - 1; bitmask = bitmask ^ ((1 << 19) - 1); ll popcnt2 = __builtin_popcount(bitmask & i); if (popcnt2 % 2 == 1){ dp1[i | (1 << j)] += dp2[i]; dp2[i | (1 << j)] += dp1[i]; } else{ dp1[i | (1 << j)] += dp1[i]; dp2[i | (1 << j)] += dp2[i]; } } } } cout << dp2[(1 << 19) - 1] << " " << dp1[(1 << 19) - 1] << endl; }