#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 20;
int N, A[N_];
bool G[N_][N_];
int B[N_], C[N_];
ll Table[N_][1<<N_];
int main() {
int i, j, k;
scanf("%d", &N);
for(i = 0; i < N; i++) scanf("%d", A+i);
for(i = 0; i < N; i++) {
for(j = A[i]; j > 0; j /= 2) if(j % 2 == 1) ++B[i];
for(j = A[i]; j > 0; j /= 3) if(j % 3 == 1) ++C[i];
}
for(i = 0; i < N; i++) for(j = i+1; j < N; j++)
G[i][j] = G[j][i] = (B[i] == B[j] || C[i] == C[j]);
for(i = 0; i < N; i++) Table[i][1<<i] = 1;
for(int state = 1; state < (1<<N); state++) {
for(i = 0; i < N; i++) if(state & (1<<i)) {
int prev = state ^ (1<<i);
for(j = 0; j < N; j++) if((prev & (1<<j)) && G[j][i]) Table[i][state] += Table[j][prev];
}
}
ll res = 0;
for(i = 0; i < N; i++) res += Table[i][(1<<N)-1];
printf("%lld\n", res);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
164928 KB |
Output is correct |
2 |
Correct |
0 ms |
164928 KB |
Output is correct |
3 |
Correct |
0 ms |
164928 KB |
Output is correct |
4 |
Correct |
0 ms |
164928 KB |
Output is correct |
5 |
Correct |
0 ms |
164928 KB |
Output is correct |
6 |
Correct |
0 ms |
164928 KB |
Output is correct |
7 |
Correct |
0 ms |
164928 KB |
Output is correct |
8 |
Correct |
0 ms |
164928 KB |
Output is correct |
9 |
Correct |
0 ms |
164928 KB |
Output is correct |
10 |
Correct |
0 ms |
164928 KB |
Output is correct |
11 |
Correct |
12 ms |
164928 KB |
Output is correct |
12 |
Correct |
12 ms |
164928 KB |
Output is correct |
13 |
Correct |
56 ms |
164928 KB |
Output is correct |
14 |
Correct |
288 ms |
164928 KB |
Output is correct |
15 |
Correct |
292 ms |
164928 KB |
Output is correct |
16 |
Correct |
272 ms |
164928 KB |
Output is correct |
17 |
Correct |
300 ms |
164928 KB |
Output is correct |
18 |
Correct |
272 ms |
164928 KB |
Output is correct |
19 |
Correct |
1608 ms |
164928 KB |
Output is correct |
20 |
Correct |
1816 ms |
164928 KB |
Output is correct |