제출 #4810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4810		cki86201	아름다운 순열 (IZhO12_beauty)	C++98	100 / 100	1136 ms	164928 KiB

beauty

#include<stdio.h>

typedef long long ll;
ll dp[1<<20][20],ans;
int inp[22],n;
bool chk[22][22];
int data[2][22];

int count1(int x,int y)
{
	int ret = 0;
	while(x){
		ret += (x%y==1);
		x/=y;
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)scanf("%d",inp+i);
	for(i=0;i<n;i++)data[0][i] = count1(inp[i],2), data[1][i] = count1(inp[i],3);
	for(i=0;i<n;i++)for(int j=0;j<n;j++)chk[i][j] = (data[0][i]==data[0][j] || data[1][i]==data[1][j]);
	for(i=0;i<n;i++)dp[0][i]=1;
	for(int b=0;b<1<<n;b++){
		for(i=0;i<n;i++){
			if(b&1<<i)continue;
			for(int j=0;j<n;j++){
				if((b|1<<i) & 1<<j)continue;
				if(chk[i][j])dp[b|1<<i][j] += dp[b][i];
			}
			if((b|1<<i)+1 == 1<<n)ans += dp[b][i];
		}
	}
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 100 / 100