fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N=26;
  6. const int mod=1e9+7;
  7. int n,a[N],dp[(1<<N)];
  8. vector<int>val,pos[N];
  9.  
  10. int calc(int mask)
  11. {
  12.     int &res=dp[mask];
  13.     if(res!=-1) return res;
  14.     res=0;
  15.     int first_bit=-1;
  16.     int second_bit=-1;
  17.     for(int i=0;i<n;i++)
  18.     {
  19.         if(mask>>i&1)
  20.         {
  21.             if(first_bit==-1) first_bit=i;
  22.             else if(second_bit==-1) second_bit=i;
  23.         }
  24.     }
  25.     if(first_bit==n-1&&second_bit==-1) return res=1;
  26.     else if(first_bit==second_bit-1) res=calc(mask-(1<<first_bit));/// ko xây thêm cây dưới đỉnh first_bit
  27.     for(int ii=0;ii<val.size();ii++)
  28.     {
  29.         for(int jj=ii;jj<val.size();jj++)
  30.         {
  31.             int x=val[ii];
  32.             int y=val[jj];
  33.             if(__gcd(x,y)!=val[a[first_bit]]) continue;
  34.             int mul=1;
  35.             if(pos[ii].empty()) continue;
  36.             mul=mul*pos[ii].size();
  37.             int i=pos[ii].back();
  38.             pos[ii].pop_back();
  39.             if(pos[jj].empty())
  40.             {
  41.                 pos[ii].push_back(i);
  42.                 continue ;
  43.             }
  44.             mul=mul*pos[jj].size();
  45.             int j=pos[jj].back();
  46.             pos[jj].pop_back();
  47.             if(x==y) mul=(1ll*mul*(mod+1)/2)%mod;
  48.             if(first_bit!=second_bit-1&&i!=first_bit+1) mul=0;/// nếu first_bit và second_bit ko liền nhau bắt buộc i phải bằng first_bit+1.
  49.             int cur_mask=mask-(1<<first_bit);/// xóa first_bit
  50.             cur_mask+=(1<<i)+(1<<j);/// them đỉnh i và j.
  51.             res=(res+1ll*calc(cur_mask)*mul%mod)%mod;
  52.             pos[jj].push_back(j);
  53.             pos[ii].push_back(i);
  54.         }
  55.     }
  56.     return res;
  57. }
  58.  
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(nullptr);
  63.     memset(dp,-1,sizeof dp);
  64.     cin>>n;
  65.     for(int i=0;i<n;i++)
  66.     {
  67.         cin>>a[i];
  68.         val.push_back(a[i]);
  69.     }
  70.     sort(val.begin(),val.end());
  71.     val.erase(unique(val.begin(),val.end()),val.end());
  72.     sort(a,a+n);
  73.     for(int i=n-1;i>=0;i--)
  74.     {
  75.         a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin();
  76.         pos[a[i]].push_back(i);
  77.     }
  78.     int sz=pos[0].size();
  79.     pos[0].pop_back();
  80.     cout<<1ll*calc(1)*sz%mod;
  81. }
  82.  
Success #stdin #stdout 0.03s 265792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/64l239
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!