제출 #1259392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259392		proofy	아름다운 순열 (IZhO12_beauty)	C++20	100 / 100	699 ms	172872 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
#define ll long long


int count_one_binary(int x) {
	return __builtin_popcount(x);
}

int count_one_ternary(int x) {
	int res = 0;
	while (x) {
		res += ((x % 3) == 1);
		x /= 3;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& u : a) cin >> u;
	
	vector<vector<int>> g(n);
	for (int i = 0; i < n; i++) g[i].reserve(n);

	for (int i = 0; i < n; i++) 
		for (int j = i + 1; j < n; j++) 
			if (count_one_binary(a[i]) == count_one_binary(a[j]) || count_one_ternary(a[i]) == count_one_ternary(a[j])) {
				g[i].push_back(j);
				g[j].push_back(i);
			}

	vector<vector<ll>> dp(n, vector<ll>(1 << n));
	for (int i = 0; i < n; i++) dp[i][(1 << n) - 1] = 1;

	for (int mask = (1 << n) - 2; mask >= 1; --mask) 
		for (int i = 0; i < n; i++) if ((1 << i) & mask) {
			for (int u : g[i]) if (((1 << u) & mask) == 0) 
				dp[i][mask] += dp[u][mask | (1 << u)];
		}
	
	ll ans = 0;
	for (int i = 0; i < n; i++) ans += dp[i][1 << i];

	cout << ans << "\n";
}

• Subtask 1: 100 / 100