제출 #1028207

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

beauty

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t
#define ar array

const int mxN=20;
int n, a[mxN];
ll dp[mxN][1<<mxN];
ar<int, 2> cnt[mxN];

ar<int, 2> calc(int x) {
    int cnt2=0, cnt3=0;
    int p=x;
    while(p) {
        if(p&1) ++cnt2;
        p/=2;
    }
    p=x;
    while(p) {
        if(p%3==1) ++cnt3;
        p/=3;
    }
    return {cnt2, cnt3};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i=0; i<n; ++i) {
        cin >> a[i];
        cnt[i]=calc(a[i]);
    }
    ll ans=0;
    for(int i=0; i<n; ++i) dp[i][1<<i]=1;
    for(int msk=1; msk<(1<<n); ++msk) {
        for(int i=0; i<n; ++i) {
            if(msk&(1<<i)) {
                for(int j=0; j<n; ++j) {
                    if(i==j) continue;
                    if(((msk&(1<<j))>0)&&((cnt[i][0]==cnt[j][0])||(cnt[i][1]==cnt[j][1]))) {
                        dp[i][msk]+=dp[j][msk^(1<<i)];
                    }
                }
            }
        }
    }
    int sz=(1<<n)-1;
    for(int i=0; i<n; ++i) ans+=dp[i][sz];
    cout << ans << "\n";
	return 0;
}

• Subtask 1: 100 / 100