#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int dp[(1<<20)][20][20];
map<int,int> forw, back;
int two[20], thre[20];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int n; cin>>n;
int a[20], ind = 0;
for(int i=0; i<n; i++) {
cin>>a[i];
int cnt = 0, x = a[i];
while(x) {
cnt += (x&1);
x = x>>1;
}
two[i] = cnt;
if(forw.find(cnt)==forw.end()) { forw[cnt] = ind, back[ind] = cnt; ind++; }
x = a[i], cnt = 0;
int b = 387420489;
while(x) {
if(b*2<=x) { x-=b*2; cout<<2;}
else if(b<=x) { x-=b; cnt++; cout<<1;}
else cout<<0;
b/=3;
}
cout<<endl;
thre[i] = cnt;
}
for(int i=0; i<n; i++) dp[(1<<i)][forw[two[i]]][thre[i]] = 1;
for(int mask = 1; mask<(1<<n); mask++) {
for(int i=0; i<n; i++) {
if(mask&(1<<i)) continue;
// try same two
for(int j=0; j<20; j++) dp[mask+(1<<i)][forw[two[i]]][thre[i]] += dp[mask][forw[two[i]]][j];
// try same three
for(int j=0; j<20; j++) dp[mask+(1<<i)][forw[two[i]]][thre[i]] += dp[mask][j][thre[i]];
// subtract repeated
dp[mask+(1<<i)][forw[two[i]]][thre[i]] -= dp[mask][forw[two[i]]][thre[i]];
}
}
int fin = 0;
for(int i=0; i<20; i++) for(int j=0; j<20; j++) fin += dp[(1<<n)-1][i][j];
cout<<fin;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
