Advertisement
Josif_tepe

Untitled

Apr 20th, 2022
682
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None
  1. #include <iostream>
  2. using namespace std;
  3. int n;
  4. int mat[22][22];
  5. long long dp[1<<20];
  6. long long rec(int visited) {
  7.     if(__builtin_popcount(visited) == n) {
  8.         return 1;
  9.     }
  10.     if(dp[visited] != -1) {
  11.         return dp[visited];
  12.     }
  13.     int at = __builtin_popcount(visited);
  14.     long long combinations = 0;
  15.     for(int j = 0; j< n  ; j++) {
  16.         if(mat[at][j] == 1) {
  17.             if((visited & (1 << j)) == 0) {
  18.                 int new_mask = (visited | (1 << j));
  19.                 combinations += rec(new_mask);
  20.             }
  21.         }
  22.     }
  23.     return dp[visited] = combinations;
  24. }
  25. int main() {
  26.     int t;
  27.     cin >> t;
  28.     while(t--) {
  29.     cin >> n;
  30.     for(int i = 0; i < n; i++) {
  31.         for(int j = 0; j < n; j++) {
  32.             cin >> mat[i][j];
  33.         }
  34.     }
  35.     memset(dp, -1, sizeof dp);
  36.     cout << rec(0) << endl;
  37.     }
  38.     return 0;
  39. }
  40.  
Advertisement
RAW Paste Data Copied
Advertisement