Advertisement
Josif_tepe

Untitled

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