fork download 
  1.     #include<bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     //macro for long long
  6.     typedef long long ll;
  7.  
  8.     ll n;
  9.  
  10.     ll a[21][21];
  11.     ll dp[2097152];
  12.  
  13.     ll rec(ll b)
  14.     {
  15.         ll res=0,pos=0;
  16.  
  17.         //finding the current position = no of 1's in binary representation of b
  18.         for(ll i=0;i<n;i++)
  19.             if(b&(1<<i))
  20.                 pos++;
  21.  
  22.         //memoization
  23.         if(dp[b]!=-1)
  24.             return dp[b];
  25.  
  26.         //if all bits in b is 1
  27.         else if(pos==n)
  28.         {
  29.             dp[b]=1;
  30.             return dp[b];
  31.         }
  32.         else
  33.         {
  34.             res=0;
  35.             for(ll i=0;i<n;i++)
  36.                 if( a[pos][i] && !( (1<<i) & b ) )
  37.                     res+=rec(( (1<<i) | b ));
  38.             dp[b]=res;
  39.             return res;
  40.         }
  41.     }
  42.  
  43.  
  44.     int main()
  45.     {
  46.         ll t,j_limit=0;
  47.         cin>>t;
  48.         while(t--)
  49.         {
  50.             cin>>n;
  51.  
  52.             //finding the maximum index till which dp array will be filled
  53.             j_limit=1;
  54.             for(ll i=0;i<=n;i++)
  55.                 j_limit*=2;
  56.  
  57.             //initializing dp array to -1
  58.             for(ll j=0;j<j_limit;j++)
  59.                 dp[j]=-1;
  60.  
  61.             //reading input
  62.             for(ll i=0;i<n;i++)
  63.                 for(ll j=0;j<n;j++)
  64.                     cin>>a[i][j];
  65.  
  66.             //calling recursion
  67.             cout<<rec(0)<<"\n";
  68.         }
  69.         return 0;
  70.     }
  71.  
Success #stdin #stdout 0s 31624KB
comments ()
stdin 
1
3
1 1 1
1 1 1
1 1 1
stdout 
6
https://ideone.com/cX3Y2N
language:
C++14 (gcc 8.3)
created:
6 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!