#include<bits/stdc++.h>
using namespace std;
int const maxn = 2005,MOD=1e9 + 7;
int d[maxn];
struct road{
int a,b,cost;
};
int pow(int a,int b){
int result = 1;
while (b>0){
if (b&1) {
result *= a;
}
a = a*a;
b = b>>1;
}
return result;
}
int gcd(int a,int b){
if (b==0) return a;
if (a<b) swap(a,b);
return gcd(b,a%b);
}
int count2(int x){
return __builtin_popcount(x);
}
int count3(int x){
int cnt=0;
while (x){
if (x%3==1) cnt++;
x/=3;
}
return cnt;
}
int dp[1<<20];
void solve(){
int n;cin>>n;
int arr[n+1];
for (int i=1;i<=n;++i) cin >> arr[i];
pair<int,int> v[n+1];
for (int i=1;i<=n;++i) v[i] = make_pair(count2(arr[i]),count3(arr[i]));
dp[0] = 1;
for (int mask=1;mask<(1<<n);++mask){
int sz=0;
for (int i=0;i<n;++i){
if ((1<<i)&mask) sz++;
}
if (sz==1) dp[mask]=1;
else{//more than 1 is selected
for (int i=0;i<n;++i){
if ((1<<i)&mask){//we are choosing the ith bit to be the one we are selecting to add
int sub_mask = mask^(1<<i);
if (dp[sub_mask]!=-1)
for (int j=0;j<n;++j){
// cout << 1;
if ((1<<j)&sub_mask and (v[j+1].first==v[i+1].first or v[j+1].second==v[i+1].second) and dp[sub_mask^(1<<j)]!=-1){
dp[mask]+=dp[sub_mask^(1<<j)];
// cout << mask <<' ';
}
}
}
}
}
if (dp[mask]==0) dp[mask] = -1;
}
cout << dp[(1<<n)-1];
// cout << dp[3];
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
