#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
vector<set<int> > graf(20);
int cnt2(int n)
{
int c=0;
while(n>0)
{
if(n%2==1)
c++;
n/=2;
}
return c;
}
int cnt3(int n)
{
int c=0;
while(n>0)
{
if(n%3==1)
c++;
n/=3;
}
return c;
}
ll dp[20][(1<<20)];
ll calc(int tr,int mask)
{
//printf("Usao za %i %i\n",tr,mask);
if(dp[tr][mask]!=-1)
return dp[tr][mask];
if(tr==0||(mask&(1))==0)
{
if(mask==0&&tr==0)
{
dp[tr][mask]=1;
return 1;
}
else
{
dp[tr][mask]=0;
return 0;
}
}
dp[tr][mask]=0;
for(auto p:graf[tr])
{
if((1<<p)&mask)
{
//printf("Pozivam za %i %i\n",p,1<<p);
dp[tr][mask]+=calc(p,(1<<p)^mask);
}
}
return dp[tr][mask];
}
int main()
{
//srand(time(NULL));
memset(dp,-1,sizeof(dp));
vector<int> connect[32][2];
int n;
scanf("%i",&n);
vector<int> niz(n);
//int a=1e9;
//int r=rand()%a+1;
bool same=true;
for(int i=0;i<n;i++)
{
//niz[i]=r;
scanf("%i",&niz[i]);
int c2=cnt2(niz[i]);
int c3=cnt3(niz[i]);
if(i>0&&niz[i]!=niz[i-1])
same=false;
//printf("%i %i\n",c2,c3);
connect[c2][0].pb(i);
//if(c2!=c3)
connect[c3][1].pb(i);
}
if(same)
{
ll res=1;
for(int i=2;i<n;i++)
res*=(ll)i;
printf("%lld\n",res);
return 0;
}
for(int i=0;i<n;i++)
{
int c2=cnt2(niz[i]);
int c3=cnt3(niz[i]);
for(auto p:connect[c2][0])
{
if(p!=i)
{
//printf("%i -> %i\n",i,p);
graf[i].insert(p);
}
}
for(auto p:connect[c3][1])
{
if(p!=i)
{
//printf("%i -> %i\n",i,p);
graf[i].insert(p);
}
}
}
//printf("gotov %i\n",clock());
for(int i=0;i<n;i++)
{
for(int m=0;m<(1<<n);m++)
{
calc(i,m);
}
}
//printf("Gotov %i\n",clock());
ll cnt=0;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int m=0;m<(1<<(n-1));m++)
{
//printf("%i\n",m);
int tr=m;
tr<<=1;
tr+=1;
if(tr&(1<<i)||tr&(1<<j))
continue;
int inverse=((1<<(n))-1)^tr;
//printf("%inverse!\n",inverse);
inverse&=((1<<(n))-1)-(1<<i);
inverse&=((1<<(n))-1)-(1<<j);
inverse+=1;
//printf("%i-%i %i-%i\n",i,tr,j,inverse);
//if((ll)calc(i,tr)*calc(j,inverse)>0)
//printf("%lld %lld %i-%i %i-%i %i\n",calc(i,tr),calc(j,inverse),i,tr,j,inverse,((1<<(n-1))-1));
cnt+=(ll)2*(ll)dp[i][tr]*dp[j][inverse];
}
}
}
//printf("Gotov2 %i\n",clock());
for(int i=1;i<n;i++)
{
int mask=((1<<n)-1)-(1<<i);
//printf("%i %i\n",i,mask);
cnt+=(ll)2*dp[i][mask];
}
printf("%lld\n",cnt);
return 0;
}
Compilation message
beauty.cpp: In function 'int main()':
beauty.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
beauty.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&niz[i]);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
164472 KB |
Output is correct |
| 2 |
Correct |
154 ms |
164596 KB |
Output is correct |
| 3 |
Correct |
130 ms |
164660 KB |
Output is correct |
| 4 |
Correct |
130 ms |
164660 KB |
Output is correct |
| 5 |
Correct |
129 ms |
164660 KB |
Output is correct |
| 6 |
Correct |
153 ms |
164704 KB |
Output is correct |
| 7 |
Correct |
133 ms |
164704 KB |
Output is correct |
| 8 |
Correct |
134 ms |
164764 KB |
Output is correct |
| 9 |
Correct |
129 ms |
164764 KB |
Output is correct |
| 10 |
Correct |
137 ms |
164764 KB |
Output is correct |
| 11 |
Correct |
151 ms |
164764 KB |
Output is correct |
| 12 |
Correct |
147 ms |
164764 KB |
Output is correct |
| 13 |
Correct |
222 ms |
164764 KB |
Output is correct |
| 14 |
Correct |
623 ms |
164900 KB |
Output is correct |
| 15 |
Correct |
691 ms |
164900 KB |
Output is correct |
| 16 |
Correct |
543 ms |
164900 KB |
Output is correct |
| 17 |
Correct |
583 ms |
164900 KB |
Output is correct |
| 18 |
Correct |
459 ms |
164900 KB |
Output is correct |
| 19 |
Correct |
2575 ms |
164900 KB |
Output is correct |
| 20 |
Correct |
2872 ms |
164900 KB |
Output is correct |
