제출 #13349

#제출 시각아이디문제언어결과실행 시간메모리
13349baneling100아름다운 순열 (IZhO12_beauty)C++98
100 / 100
1255 ms173116 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...