제출 #13348

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

beauty

#include <stdio.h>
#define N_MAX 20
#define BIT_MAX 1048575

int N, M=1, A[N_MAX+1], B[N_MAX+1][N_MAX+1];
long long D[N_MAX+1][BIT_MAX+1], Ans;

int binaryOne(int num) {

    int i, cnt=0;

    for(i=1 ; i<=num ; i<<=1)
        if(num&i)
            cnt++;
    return cnt;
}

int ternaryOne(int num) {

    int cnt=0;

    while(num) {
        if(num%3==1)
            cnt++;
        num/=3;
    }
    return cnt;
}

void bitMask(int x, int y) {

    int i;

    for(i=1 ; i<=N ; i++)
        if(B[x][i] && y&(1<<(i-1))) {
            if(!D[i][y-(1<<(x-1))])
                bitMask(i,y-(1<<(x-1)));
            D[x][y]+=D[i][y-(1<<(x-1))];
        }
}

int main(void) {

    int i, j;

    scanf("%d",&N);
    for(i=1 ; i<=N ; i++)
        scanf("%d",&A[i]);
    for(i=1 ; i<=N ; i++)
        for(j=1 ; j<=N ; j++)
            if(i!=j && (binaryOne(A[i])==binaryOne(A[j]) || ternaryOne(A[i])==ternaryOne(A[j])))
                B[i][j]=1;
    for(i=1 ; i<=N ; i++) {
        M<<=1;
        D[i][1<<(i-1)]=1;
    }
    M--;
    for(i=1 ; i<=N ; i++) {
        bitMask(i,M);
        Ans+=D[i][M];
    }
    printf("%lld",Ans);

    return 0;
}

• Subtask 1: 60 / 100