#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
//void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
const int N = (1 << 21) + 1;
long long dp[N][21];
int a[21], bit[21], ter[21];
long long ful;
int getbits(int x){
int res = 0;
while(x > 0){
res += x % 2;
x >>= 1;
}
return res;
}
int getter(int x){
int res = 0;
while(x > 0){
res += (x % 3 == 1);
x /= 3;
}
return res;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
ful += (1 << i);
cin >> a[i];
bit[i] = getbits(a[i]);
ter[i] = getter(a[i]);
dp[(1 << i)][i] = 1;
}
for(int i = 1; i < (1 << (n + 1)); i++){
for(int j = 1; j <= n; j++){
if(dp[i][j] == 0 || (i & (1 << j)) == 0)continue;
for(int k = 1; k <= n; k++){
if((i & (1 << k)) || i + (1 << k) <= ful)continue;
if(bit[k] == bit[j] || ter[k] == ter[j])
dp[i + (1 << k)][k] += dp[i][j];
}
}
}
long long ans = 0;
for(int i = 1; i <= n; i++){
ans += dp[ful][i];
}
cout << ans;
}
Compilation message
beauty.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
33 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
