| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 969760 | 2024-04-25T14:39:21 Z | VMaksimoski008 | 아름다운 순열 (IZhO12_beauty) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
int C(int x) {
int cnt = 0;
while(x) {
if(x % 3 == 1) cnt++;
x /= 3;
}
return cnt;
}
int cnt(int x) { return __builtin_popcount(x); }
int dp[20][1<<20], n, ans, v[20];
int main() {
cin >> n;
for(int i=0; i<n; i++) cin >> v[i];
vector<int> graph[n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(i != j && (cnt(v[i]) == cnt(v[j]) || C(v[i]) == C(v[j])))
graph[i].push_back(j);
for(int i=0; i<n; i++) dp[i][1<<i] = 1;
for(int s=1; s<(1<<n); s++) {
for(int i=0; i<n; i++) {
if((s & (1 << i)) == 0) continue;
for(int &j : graph[i])
if(s & (1 << j)) dp[i][s] += dp[j][s^(1<<i)];
}
}
for(int i=0; i<n; i++) ans += dp[i][(1<<n)-1];
cout << ans << '\n';
return 0;
}