#include <bits/stdc++.h>
#define N 21
#define M ((1<<20) + 100)
using namespace std;
typedef long long ll;
int n, v[N], pot[45], qtd[N][5];
ll dp[N][M];
bool equal(int a, int b)
{
return (qtd[a][2] == qtd[b][2] || qtd[a][3] == qtd[b][3]);
}
int ternary(int x)
{
int cnt = 0;
for(int log3 = 30; log3 >= 0; log3 --)
{
ll aux = pot[log3], qaux = 0;
if(x >= aux)
{
x -= aux;
qaux ++;
}
if(x >= aux)
{
x -= aux;
qaux ++;
}
cnt = cnt + (qaux == 1);
}
return cnt;
}
ll solve(int x, int mask)
{
if(dp[x][mask] != -1) return dp[x][mask];
if(mask == (1<<n) - 1) return 1;
dp[x][mask] = 0;
for(int v = 0; v < n; v++)
{
if(mask & (1<<v)) continue;
if(equal(x, v)) dp[x][mask] += solve(v, mask | (1<<v));
}
return dp[x][mask];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 0; i < n; i++) cin>>v[i];
pot[0] = 1;
for(int i = 1; i < 45; i++) pot[i] = pot[i - 1]*3;
for(int i = 0; i < n; i++)
{
qtd[i][2] = __builtin_popcount (v[i]);
qtd[i][3] = ternary(v[i]);
}
memset(dp, -1, sizeof dp);
ll best = 0;
for(int i = 0; i < n; i++) best += solve(i, 1<<i);
cout<<best<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
172792 KB |
Output is correct |
| 2 |
Incorrect |
125 ms |
172792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
