제출 #499962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499962		ac2hu	아름다운 순열 (IZhO12_beauty)	C++14	100 / 100	2790 ms	164452 KiB

beauty

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
	int n;cin >> n;
	vector<int> t2(n),t3(n);
	for(int i = 0;i<n;i++){
		int a;cin >> a;
		t2[i] = 0;
		t3[i] = 0;
		int temp  =a;
		while(temp != 0){
			if(temp%2 == 1)
				t2[i]++;
			temp /= 2;
		}
		temp = a;
		while(temp != 0){
			if(temp%3 == 1)
				t3[i]++;
			temp /= 3;
		}
	}
	int dp[n][(1 << n)];
	for(int j = 1;j<(1 << n);j++){
		for(int i = 0;i<n;i++){
			dp[i][j] = 0;
		}
	}
	for(int i = 0;i<n;i++)
		dp[i][(1 << i)] = 1;
	for(int j = 1;j<(1 << n);j++){
		vector<int> selected;
		for(int i = 0;i<n;i++){
			if(j&(1 << i))
				selected.push_back(i);
		}
		for(int e : selected){
			for(int f : selected){
				if(e != f){
					if(t2[e] == t2[f] || t3[e] == t3[f]){
						dp[e][j] += dp[f][j^(1 << e)];
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0;i<n;i++)
		ans += dp[i][(1 << n) - 1];
	cout << ans;
}
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int T = 1;
	//cin >> T;
	while(T--){
		solve();
	}
}

• Subtask 1: 100 / 100