diff options
Diffstat (limited to '21.5/feb/gold/gifts.cpp')
-rw-r--r-- | 21.5/feb/gold/gifts.cpp | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/21.5/feb/gold/gifts.cpp b/21.5/feb/gold/gifts.cpp new file mode 100644 index 0000000..023ce6b --- /dev/null +++ b/21.5/feb/gold/gifts.cpp @@ -0,0 +1,58 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair<int, int>; +const int MX = 18; + +int A[MX][MX]; +ll B[1<<MX], DP[1<<MX], cnt[1<<MX][MX][MX]; + +int main() { + cin.tie(0)->sync_with_stdio(0); + int N; cin >> N; + for (int i = 0; i < N; ++i) { + for (int j = 0; j < N; ++j) { + int x; cin >> x; + A[i][x-1] = j; + } + } + for (int i = 0; i < N; ++i) + for (int j = 0; j < N; ++j) if (i != j && A[j][i] <= A[j][j]) + cnt[1<<i|1<<j][i][j] = 1; + for (int m = 0; m < 1<<N; ++m) { + for (int i = 0; i < N; ++i) if (m&1<<i) { + for (int j = 0; j < N; ++j) if (i != j && m&1<<j) { + if (A[i][j] <= A[i][i]) B[m] += cnt[m][i][j]; + for (int k = 0; k < N; ++k) if (!(m&1<<k) && A[k][j] <= A[k][k]) + cnt[m|1<<k][i][k] += cnt[m][i][j]; + } + } + } + for (int m = 1; m < 1<<N; ++m) { + B[m] /= __builtin_popcount(m); + if (__builtin_popcount(m) == 1) ++B[m]; + DP[m] = B[m]; + } + for (int m = 0; m < 1<<N; ++m) + for(int i = m; i; i = i-1&m) + if (__builtin_clz(m) == __builtin_clz(i)) DP[m] += B[i]*DP[m^i]; + DP[0] = 1; + int Q; cin >> Q; + while (Q--) { + string S; cin >> S; + int m = 0; + for (int i = 0; i < N; ++i) if (S[i] == 'H') + m |= 1<<i; + cout << DP[m]*DP[(1<<N)-1^m] << '\n'; + } +} + +/* +for i in (seq 18) + ./1<p/{$i}.in>out + diff out p/{$i}.out + echo $i OK +end +*/
\ No newline at end of file |