#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int cnt2[25], cnt3[25];
int dp[1 << 20][20];
vector<int> G[25];
int ter(int x)
{
int res = 0;
while (x > 0)
{
res = (x % 3 == 1);
x /= 3;
}
return res;
}
void build()
{
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (cnt2[i] == cnt2[j] || cnt3[i] == cnt3[j])
{
G[i].push_back(j);
G[j].push_back(i);
}
}
}
}
void xuly()
{
build();
int last = (1 << n) - 1;
for (int i = 0; i < n; ++i) dp[1 << i][i] = 1;
for (int mask = 0; mask <= last; ++mask)
{
for (int i = 0; i < n; ++i)
{
if (((mask >> i) & 1) == 0) continue;
for (int j : G[i])
{
if (((mask >> j) & 1) == 1) continue;
int p = mask + (1 << j);
dp[p][j] += dp[mask][i];
}
}
}
int res = 0;
for (int i = 0; i < n; ++i) res += dp[last][i];
cout << res;
}
void nhap()
{
int x;
cin >> n;
for (int i = 0; i < n; ++i) cin >> x, cnt2[i] = __builtin_popcount(x), cnt3[i] = ter(x);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
nhap();
xuly();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
