#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 21 , LOG = 30;
int n;
vector<int> a(N);
vector<vector<int>> dp(N , vector<int>(1 << N)) , v2(LOG) , v3(LOG) , v(N);
int ternary_ones(int x){
int cnt = 0;
while(x > 0){
cnt += (x % 3 == 1);
x /= 3;
}
return cnt;
}
main(){
cin >> n;
for(int i = 1;i <= n;i ++){
cin >> a[i];
v2[__builtin_popcount(a[i])].push_back(i);
v3[ternary_ones(a[i])].push_back(i);
}
for(int i = 1;i <= n;i ++){
for(int x : v2[__builtin_popcount(a[i])]){
if(x != i){
v[i].push_back(x);
}
}
for(int x : v3[ternary_ones(a[i])]){
if(x != i){
v[i].push_back(x);
}
}
v[i].push_back(0);
}
dp[0][0] = 1;
for(int mask = 0;mask < (1 << n);mask ++){
for(int x = 1;x <= n;x ++){
if(mask >> (x - 1) & 1){
for(int y : v[x]){
if(y == 0 || (mask >> (y - 1) & 1)){
dp[x][mask] += dp[y][mask ^ (1 << (x - 1))];
}
}
}
}
}
int ans = 0;
for(int x = 1;x <= n;x ++){
ans += dp[x][(1 << n)- 1];
}
cout << ans << endl;
}
Compilation message
beauty.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
16 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
