제출 #346395

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

beauty

#include <bits/stdc++.h>
#define DIM 1048580
#define DIMN 21
using namespace std;

long long dp[DIM][DIMN];
int f[DIMN],p[DIMN],v[DIMN];
vector <int> L[DIMN];
int n,i,j;

int countt (int x){

    memset (f,0,sizeof f);

    while (x){
        int p = 1, exp = 0;
        while (p * 3 <= x){
            p *= 3;
            exp++;
        }

        f[exp]++;
        x -= p;
    }

    int sol = 0;
    for (int i=0;i<=19;i++)
        if (f[i] == 1)
            sol++;

    return sol;

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i];

    p[0] = 1;
    for (i=1;i<=19;i++)
        p[i] = p[i-1] * 3;

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++){
            if (__builtin_popcount(v[i]) == __builtin_popcount(v[j]) || countt(v[i]) == countt(v[j])){
                L[i].push_back(j);
                L[j].push_back(i);
                //cout<<i<<" "<<j<<"\n";
            }
        }

    for (i=1;i<=n;i++)
        dp[(1<<(i-1))][i] = 1;

    for (int mask=1;mask<(1<<n);mask++){
        if (__builtin_popcount(mask) <= 1)
            continue;

        for (i=1;i<=n;i++){
            if (!(mask&(1<<(i-1))))
                continue;

            for (auto vecin : L[i]){
                if (!(mask&(1<<(vecin-1))))
                    continue;

                dp[mask][i] += dp[mask-(1<<(i-1))][vecin];

            }}}

    long long sol = 0;
    for (i=1;i<=n;i++)
        sol += dp[(1<<n)-1][i];

    cout<<sol;

    return 0;
}

• Subtask 1: 100 / 100