제출 #874926

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

beauty

// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int ter(int n) {
    int cnt = 0;
    while (n) {
        cnt += n % 3 == 1;
        n /= 3;
    }
    return cnt;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    vector can(n, vector(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            can[i][j] = __builtin_popcount(a[i]) == __builtin_popcount(a[j]) or ter(a[i]) == ter(a[j]);
        }
    }
    vector dp(n, vector(1 << n, 0ll));
    for (int i = 0; i < n; i++) dp[i][1 << i] = 1;
    for (int bt = 0; bt < (1 << n); bt++) {
        for (int i = 0; i < n; i++) {
            if (!(bt & (1 << i))) continue;
            for (int j = 0; j < n; j++) {
                if (bt & (1 << j)) continue;
                if (can[i][j]) dp[j][bt | (1 << j)] += dp[i][bt];
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) ans += dp[i][(1 << n) - 1];
    cout << ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
    // cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

• Subtask 1: 100 / 100