제출 #638856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638856		MohamedAhmed04	아름다운 순열 (IZhO12_beauty)	C++14	0 / 100	101 ms	262144 KiB

beauty

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 21 ;

int arr[MAX] ;
int n ;

int cnt2[MAX] , cnt3[MAX] ;

int calc(int x)
{
	int cnt = 0 ;
	while(x > 0)
	{
		cnt += (x%3 == 1) ;
		x /= 3 ;
	}
	return cnt ;
}

long long dp[MAX][(1 << MAX)] ;

long long solve(int idx , int mask)
{
	if(mask == (1 << n) - 1)
		return 1 ;
	long long &ret = dp[idx][mask] ;
	if(ret != -1)
		return ret ;
	ret = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if((mask & (1 << i)))
			continue ;
		if(cnt2[i] == cnt2[idx] || cnt3[i] == cnt3[idx])
			ret += solve(i , mask | (1 << i)) ;
	}
	return ret ;
}

int main()
{
	memset(dp , -1 , sizeof(dp)) ;
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n ; ++i)
		cnt2[i] = __builtin_popcount(arr[i]) , cnt3[i] = calc(arr[i]) ;
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
		ans += solve(i , 1 << i) ;
	return cout<<ans<<"\n" , 0 ;
}		

• Subtask 1: 0 / 100