제출 #16865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16865		murat	아름다운 순열 (IZhO12_beauty)	C++98	60 / 100	2570 ms	83644 KiB

beauty

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int F, dp[20][1 << 20], n, m, c[20][20], a[20];

int take2(int x) { int sum = 0; while(x) { sum += (x % 2 == 1); x /= 2; } return sum; }
int take3(int x) { int sum = 0; while(x) { sum += (x % 3 == 1); x /= 3; } return sum; }

ll f(int node, int mask) {
    if(mask == F) return 1;
    int &r = dp[node][mask];
    if(r != -1) return r;
    r = 0;
    FOR(i, 0, n)
        if(!(mask & (1 << i)) && c[node][i])
            r += f(i, mask | (1 << i));
    return r;
}

int main() {
    scanf("%d",&n); F = (1 << n) - 1; --n;
    FOR(i, 0, n)
        scanf("%d", &a[i]);
    FOR(i, 0, n)
        FOR(j, 0, n)
            if(i != j && (take2(a[i]) == take2(a[j]) || take3(a[i]) == take3(a[j]))) {
                c[i][j] = 1;
            }
    memset(dp, -1, sizeof dp);
    ll ans = 0;
    FOR(i, 0, n)
        ans += f(i, (1 << i));
    cout << ans << endl;
    return 0;
}

• Subtask 1: 60 / 100