제출 #867647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867647		sleepntsheep	아름다운 순열 (IZhO12_beauty)	C++17	0 / 100	1400 ms	262144 KiB

beauty

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 22

int n, a[N], b3[N];
ll ans, dp[N][1<<N][2];

inline int beautiful(int i, int j) { return (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) || b3[i] == b3[j]; }

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        for (int x = a[i]; x; b3[i] += (x % 3) == 1, x /= 3);
        dp[i][1<<i][1] = 1;
    }
    for (int k = 0; k < (1 << n); ++k)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!(k&(1<<j))) continue;
            if (dp[j][k][0]) continue;
            for (int l = 0; l < n; ++l)
            {
                if (k & (1 << l))
                {
                    if (beautiful(j, l)) dp[j][k][1] += dp[l][k&~(1<<j)][1];
                    else dp[j][k][0] += dp[l][k&~(1<<j)][1];
                }
            }
        }
    }

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

    return 0;
}

• Subtask 1: 0 / 100