제출 #336125

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

beauty

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
#define ll long long
int n, a[N], binary[N], ternary[N];
ll dp[1 << N][N];
int main() {
    cin >> n; 
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        binary[i] = __builtin_popcount(a[i]);
        for(int p = a[i]; p > 0; p /= 3) {
            if((p % 3) == 1) {
                ++ternary[i];
            }
        }
    }
    for(int mask = 0; mask < (1 << n); ++mask) {
        for(int i = 0; i < n; ++i) {
            if(mask >> i & 1) {
                int s_mask = mask ^ (1 << i);
                if(s_mask == 0) {
                    dp[mask][i] = 1;
                    continue;
                }
                for(int j = 0; j < n; ++j) {
                    if(s_mask >> j & 1) {
                        if(ternary[i] == ternary[j] || binary[i] == binary[j]) {
                            dp[mask][i] += dp[s_mask][j];
                        }
                    }
                }
            }
        }  
    }
    ll ans = 0; 
    for(int i = 0; i < n; ++i) {
        ans += dp[(1 << n) - 1][i];
    }
    cout << ans << '\n';
}

• Subtask 1: 100 / 100