Submission #13349

#	Time	Username	Problem	Language	Result	Execution time	Memory
13349		baneling100	Beautiful row (IZhO12_beauty)	C++98	100 / 100	1255 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;
}

int main(void) {

    int i, j, k;

    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<=M ; i++)
        for(j=1 ; j<=N ; j++)
            if(i&(1<<(j-1)))
                for(k=1 ; k<=N ; k++)
                    if(B[j][k] && i&(1<<(k-1)))
                        D[j][i]+=D[k][i-(1<<(j-1))];
    for(i=1 ; i<=N ; i++)
        Ans+=D[i][M];
    printf("%lld",Ans);

    return 0;
}

• Subtask 1: 100 / 100