Submission #856496

#	Time	Username	Problem	Language	Result	Execution time	Memory
856496		aykhn	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	713 ms	164696 KiB

beauty

#include <bits/stdc++.h>

// author : aykhn

using namespace std;
typedef long long ll;

#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 20;

int n;
int a[MXN];
pii cnt[MXN];
int dp[(1 << MXN)][MXN];

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
        for (int j = 0; j <= 30; j++)
        {
            cnt[i].fi += a[i] >> j & 1;
        }
        int pw = 387420489;
        int y = a[i];
        while (pw)
        {
            int x = y/pw;
            cnt[i].se += (x == 1);
            y -= x * pw;
            pw /= 3;
        }
    }
    for (int i = 0; i < n; i++) dp[(1 << i)][i] = 1;
    for (int mask = 0; mask < (1 << n); mask++)
    {
        if (bpc(mask) <= 1) continue;
        for (int i = 0; i < n; i++)
        {
            if (!(mask >> i & 1)) continue;
            for (int j = 0; j < n; j++)
            {
                if (!(mask >> j & 1)) continue;
                if (cnt[i].fi == cnt[j].fi || cnt[i].se == cnt[j].se) dp[mask][i] += dp[(mask ^ (1 << i))][j];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) res += dp[(1 << n) - 1][i];
    cout << res << '\n';
    
    
}

• Subtask 1: 100 / 100