제출 #902535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902535		tvladm2009	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	1051 ms	205652 KiB

beauty

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<ll>> dp(1 << 20, vector<ll>(n, 0));
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> bin(n), ter(n);
    for (int i = 0; i < n; ++i) {
        bin[i] = __builtin_popcount(a[i]);
        int n = a[i];
        while (n > 0) {
            if (n % 3 == 1) ++ter[i];
            n /= 3;
        }
    }
    for (int i = 0; i < n; ++i) dp[1 << i][i] = 1;
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) == 1) continue;
        for (int b = 0; b < n; ++b) {
            if (mask & (1 << b)) {
                for (int b2 = 0; b2 < n; b2++) {
                    if (!(mask & (1 << b2))) continue;
                    if (b2 != b && (bin[b] == bin[b2] || ter[b] == ter[b2])) dp[mask][b] += dp[mask - (1 << b)][b2];
                }
            }
        }
    }
    ll ans = 0;
    for (int b = 0; b < n; ++b) {
        ans += dp[(1 << n) - 1][b];
    }
    cout << ans << endl;
    return 0;
}

• Subtask 1: 100 / 100