fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. long long dp[1<<20][20];
  5.  
  6. int main(){
  7.     cin >> n;
  8.  
  9.     for(int i=0;i<n;i++)
  10.         dp[1<<i][i] = 1;
  11.  
  12.     for(int mask=0; mask<(1<<n); mask++){
  13.         for(int last=0; last<n; last++){
  14.             if(!(mask&(1<<last))) continue;
  15.             long long cur = dp[mask][last];
  16.             if(cur==0) continue;
  17.  
  18.             for(int x=0; x<n; x++){
  19.                 if(mask&(1<<x)) continue;
  20.                 if(abs(x - last) == 1) continue;
  21.                 dp[mask|(1<<x)][x] += cur;
  22.             }
  23.         }
  24.     }
  25.  
  26.     long long ans = 0;
  27.     for(int i=0;i<n;i++)
  28.         ans += dp[(1<<n)-1][i];
  29.  
  30.     cout << ans;
  31. }
  32.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
stdout
copy 
14
https://ideone.com/tnqToy
language:
C++14 (gcc 8.3)
created:
17 hours 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!