제출 #969761

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

beauty

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

int C(int x) {
    int cnt = 0;
    while(x) {
        if(x % 3 == 1) cnt++;
        x /= 3;
    }
    return cnt;
}

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

int dp[20][1<<20], n, ans, v[20];

int32_t main() {
    cin >> n;
    for(int i=0; i<n; i++) cin >> v[i];

    vector<int> graph[n];
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i != j && (cnt(v[i]) == cnt(v[j]) || C(v[i]) == C(v[j])))
                graph[i].push_back(j);

    for(int i=0; i<n; i++) dp[i][1<<i] = 1;

    for(int s=1; s<(1<<n); s++) {
        for(int i=0; i<n; i++) {
            if((s & (1 << i)) == 0) continue;
            for(int &j : graph[i])
                if(s & (1 << j)) dp[i][s] += dp[j][s^(1<<i)];
        }
    }

    for(int i=0; i<n; i++) ans += dp[i][(1<<n)-1];
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 100 / 100