#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
bool check(int a, int b){
int x = a, y = b;
int b1 = 0, b2 = 0;
while(x){
b1 += (x%2 == 1);
x /= 2;
}
while(y){
b2 += (y%2 == 1);
y /= 2;
}
if(b1 == b2) return 1;
x = a, y = b, b1 = 0, b2 = 0;
while(x){
b1 += (x%3 == 1);
x /= 2;
}
while(y){
b2 += (y%3 == 1);
y /= 2;
}
return b1 == b2;
}
bool moze[25][25];
ll dp[1500005][25];
ll a[25];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n;
cin >> n;
for(int i=0; i<n; i++){
cin >> a[i];
}
for(int i=0; i<n; i++){
dp[1<<i][i] = 1;
for(int j=0; j<n; j++){
moze[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;
dp[mask|(1<<j)][j] += dp[mask][i]*moze[i][j];
}
}
}
ll res = 0;
for(int i=0; i<n; i++) res += dp[(1<<n)-1][i];
cout << res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
