제출 #498859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498859		Gurban	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	547 ms	164372 KiB

beauty

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=20;
const int B = (1<<20);
int n;
ll dp[B][maxn];
int a[maxn],jog[maxn][maxn];

int ok(int x,int y){
	int cp = 0,sg = 0;
	int nwx = x,nwy = y;
	while(nwx){
		cp += (nwx%2);
		nwx /= 2;
	}
	while(nwy){
		sg += (nwy%2);
		nwy /= 2;
	}
	// if(x == 5 and y == 6) cout<<cp<<' '<<sg<<'\n';
	if(cp == sg) return 1;
	cp = sg = 0;
	while(x){
		cp += ((x%3) == 1);
		x /= 3;
	}
	while(y){
		sg += ((y%3) == 1);
		y /= 3;
	}
	return (cp == sg);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
		dp[(1<<i)][i] = 1;
	}
	for(int i = 0;i < n;i++){
		for(int j = i+1;j < n;j++){
			int nw = ok(a[i],a[j]);
			jog[i][j] = jog[j][i] = nw;
		}
	}

	// cout<<jog[0][2]<<'\n';

	int go = (1<<n);
	for(int i = 3;i < go;i++){
		vector<int>nw;
		for(int j = 0;j < n;j++) if((1<<j) & i) nw.push_back(j);
		for(int j = 0;j < (int)nw.size();j++){
			int now = i ^ (1<<nw[j]);
			for(int k = 0;k < (int)nw.size();k++){
				if(j == k or !jog[nw[j]][nw[k]]) continue;
				dp[i][nw[j]] += dp[now][nw[k]];
			}
		}
	}
	ll ans = 0;
	for(int i = 0;i < n;i++) ans += dp[go - 1][i];
	// for(int i = 1;i < go;i++){
	// 	cout<<i<<" ---> ";
	// 	for(int j = 0;j < n;j++) cout<<dp[i][j]<<' ';
	// 	cout<<'\n';
	// }
	cout<<ans;
}

• Subtask 1: 100 / 100