답안 #89815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89815 2018-12-18T13:01:23 Z Vardanyan 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
2 ms 376 KB
#include <bits/stdc++.h>
using namespace std;
const int N = 22;
int a[N];
bool d[N][N];
bool check(int x,int y){
    int xx,yy;
    xx = yy = 0;
    for(int i = 0;i<33;i++){
        if((x>>i)&1) xx++;
        if((y>>i)&1) yy++;
    }
    if(xx == yy) return true;
    xx = yy = 0;
    while(x!=0){
        if(x%3 == 1) xx++;
        x/=3;
    }
    while(y!=0){
        if(y%3 == 1) yy++;
        y/=3;
    }
    return xx == yy;
}
long long dp[(1<<N)][N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++) cin>>a[i];
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            if(check(a[i],a[j])){
                d[i][j] = d[j][i] = 1;
            }
        }
        dp[(1<<i)][i] = 1;
    }
    for(int mask = 1;mask<(1<<n);mask++){
        for(int lst = 0;lst<n;lst++){
            if(!((mask>>lst)&1)) continue;
            for(int i = 0;i<n;i++){
                if((mask>>i)&1) continue;
                if(d[lst][i]){
                    dp[mask|(1<<i)][i]+=dp[mask][lst];
                }
            }
        }
    }
    long long ans = 0;
    for(int lst = 0;lst<n;lst++) ans+=dp[(1<<n)-1][lst];
    cout<<ans<<endl;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -