제출 #342987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342987		apostoldaniel854	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	838 ms	164588 KiB

beauty

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 20;
bool good[MAX_N][MAX_N];
int a[MAX_N];

ll dp[1 << MAX_N][MAX_N];
int get (int x, int k) {
    int cnt = 0;
    while (x) {
        if (x % k == 1)
            cnt++;
        x /= k;
    }
    return cnt;
}
bool check (int x, int y) {
    return (get (x, 3) == get (y, 3)) || (get (x, 2) == get (y, 2));
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            good[i][j] = check (a[i], a[j]);
    for (int mask = 0; mask < (1 << n); mask++) {
        if (mask == 0) {
            for (int j = 0; j < n; j++)
                dp[1 << j][j] = 1;
        }
        else {
            for (int j = 0; j < n; j++)
                if (mask & (1 << j))
                    for (int k = 0; k < n; k++)
                        if (not (mask & (1 << k)) && good[j][k])
                            dp[mask ^ (1 << k)][k] += dp[mask][j];
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100