2022 feb gold problem 1

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