#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[(1<<20)][20];
bool check(int a, int b) {
int bina = __builtin_popcount(a);
int binb = __builtin_popcount(b);
if (bina == binb) return true;
int tera = 0, terb = 0;
while(a > 0) {
if (a % 3 == 1) tera++;
a /= 3;
}
while(b > 0) {
if (b % 3 == 1) terb++;
b /= 3;
}
return tera == terb;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int a[n];
bool mat[n][n];
for(int i = 0; i < n; i++) {
cin >> a[i];
dp[0][i] = 1;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if (i == j) continue;
mat[i][j] = check(a[i], a[j]);
}
}
for(int mask = 0; mask < (1 << n); mask++) {
for(int i = 0; i < n; i++) {
if (!(mask&(1<<i))) continue;
for(int j = 0; j < n; j++) {
if (!(mask&(1<<j))) continue;
if (!mat[i][j]) continue;
dp[mask][i] += dp[mask^(1 << i)][j];
}
}
}
ll ans = 0LL;
for(int i = 0; i < n; i++) {
ans += dp[(1 << n)-1][i];
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
