#include<iostream>
#include<algorithm>
using namespace std;
int n;
int cnt2[25];
int cnt3[25];
long long dp[1100000][20][2];
int calc_cnt2(int x)
{
int rez=0;
for(int i=0;i<30;i++)
{
if(((1<<i)&x))
rez++;
}
return rez;
}
int calc_cnt3(int x)
{
int rez=0;
while(x>0)
{
if(x%3==1)
rez++;
x/=3;
}
return rez;
}
signed main()
{
cin>>n;
int a;
for(int i=0;i<n;i++)
{
cin>>a;
cnt2[i] = calc_cnt2(a);
cnt3[i] = calc_cnt3(a);
}
for(int config=1;config<(1<<n);config++)
{
for(int cur=0;cur<n;cur++)
{
if(((1<<cur)&config)==0)
continue;
int cate=0;
for(int ult=0;ult<n;ult++)
{
if(ult!=cur && ((1<<ult)&config))
{
cate++;
if(cnt2[ult]==cnt2[cur] || cnt3[ult]==cnt3[cur])
{
dp[config][cur][1] += dp[config-(1<<cur)][ult][0] + dp[config-(1<<cur)][ult][1];
}
else
{
dp[config][cur][0] += dp[config-(1<<cur)][ult][1];
}
}
}
if(cate==0)
{
dp[config][cur][0] = 1;
dp[config][cur][1] = 0;
}
}
}
long long sum=0;
for(int ult=0;ult<n;ult++)
sum += dp[(1<<n)-1][ult][1];
cout<<sum;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
