#include <bits/stdc++.h>
using namespace std;
const int N = 22;
int a[N];
bool d[N][N];
bool check(int x,int y){
int xx,yy;
xx = yy = 0;
for(int i = 0;i<33;i++){
if((x>>i)&1) xx++;
if((y>>i)&1) yy++;
}
if(xx == yy) return true;
xx = yy = 0;
while(x!=0){
if(x%3 == 1) xx++;
x/=3;
}
while(y!=0){
if(y%3 == 1) yy++;
y/=3;
}
return xx == yy;
}
long long dp[(1<<N)][N];
int main(){
int n;
cin>>n;
for(int i = 0;i<n;i++) cin>>a[i];
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(check(a[i],a[j])){
d[i][j] = d[j][i] = 1;
}
}
dp[(1<<i)][i] = 1;
}
for(int mask = 1;mask<(1<<n);mask++){
for(int lst = 0;lst<n;lst++){
if(!((mask>>lst)&1)) continue;
for(int i = 0;i<n;i++){
if((mask>>i)&1) continue;
if(d[lst][i]){
dp[mask|(1<<i)][i]+=dp[mask][lst];
}
}
}
}
long long ans = 0;
for(int lst = 0;lst<n;lst++) ans+=dp[(1<<n)-1][lst];
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
