#include <bits/stdc++.h>
using namespace std;
#define int long long
#define A first
#define B second
bool comp[20][20];
int arr[20];
int n;
int brute(int i , int last , int mask){
if (mask == (1<<n)-1) return 1;
else if (i == n) return 0;
// if (~dp[i][last][mask]) return dp[i][last][mask];
int ans = 0;
for (int j = 0 ; j < n ; j++){
if (!(mask & (1<<j)) && (comp[last][j] || last == 20)) ans+=brute(i+1 , j , (mask | (1<<j)));
}
return ans;
}
int co(int x , int b){
int a = 0;
x = arr[x];
while(x > 0){
if (x%b == 1) a++;
x/=b;
}
return a;
}
void doWork(){
cin >> n;
for (int i = 0 ; i < n ; i++) cin >> arr[i];
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n ; j++){
if (co(i , 2) == co(j , 2) || co(i , 2) == co(j , 3) || co(i , 3) == co(j , 3) || co(i , 3) == co(j , 2)) {
comp[i][j] = 1;
}
}
}
cout << brute(0 , 20 , 0);
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
doWork();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
