joylintp

Untitled

Oct 23rd, 2021
909
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //{
  5. //#pragma gcc optimize("Ofast,unroll-loops")
  6. //#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
  7. //#define int long long
  8. //#define double long double
  9. #define MP make_pair
  10. #define F first
  11. #define S second
  12. #define MOD 1000000007
  13. #define INF 9000000000000000000LL
  14. //}
  15.  
  16. int n, g[20];
  17.  
  18. int fpow(int a, int b)
  19. {
  20.     a %= MOD;
  21.     int ret = 1;
  22.     while (b)
  23.     {
  24.         if (b & 1)
  25.             ret = (long long)ret * a % MOD;
  26.         a = (long long)a * a % MOD;
  27.         b >>= 1;
  28.     }
  29.     return ret;
  30. }
  31.  
  32. int dfs(int now, int status)
  33. {
  34.     if (now == 0)
  35.         return !status;
  36.  
  37.     int ret = 0;
  38.     for (int i = 0; i < n; i++)
  39.         if ((status & (1 << i)) && (g[i] & (1 << now)))
  40.         {
  41.             int cnt = 0;
  42.             for (int j = 0; j < n; j++)
  43.                 if ((g[i] & (1 << j)) && (status & (1 << j)))
  44.                     cnt++;
  45.             ret = (ret + (long long)dfs(i, status ^ (1 << i)) * fpow(cnt + 1, MOD - 2) % MOD) % MOD;
  46.         }
  47.     return ret;
  48. }
  49.  
  50. signed main()
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.  
  55.     cin >> n;
  56.     for (int i = 0; i < n; i++)
  57.         for (int j = 0; j < n; j++)
  58.         {
  59.             int t;
  60.             cin >> t;
  61.             if (t)
  62.                 g[i] |= (1 << j);
  63.         }
  64.  
  65.     for (int i = 0; i < n; i++)
  66.     {
  67.         int ans = 0;
  68.         for (int j = 0; j < (1 << n); j++)
  69.             if ((j & g[i]) == g[i] && (j & 1))
  70.                 ans += dfs(i, j);
  71.         cout << ans << " \n"[i == n - 1];
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
  77. //      *****  *****  *   *  *      *****  *   *  *****  *****
  78. //        *   *   *  *   *  *        *    **  *    *    *   *
  79. //       *   *   *  *****  *        *    * * *    *    *****
  80. //   *  *   *   *    *    *        *    *  **    *    *
  81. //  ****   *****    *    *****  *****  *   *    *    *
  82.  
  83. //     *   *   ***   *   *  **
  84. //    *   *  *   *  *   *  **
  85. //   * * *  *****  *****  **
  86. //  * * *  *   *  *   *
  87. //  * *   *   *  *   *  **
  88.  
Advertisement
Add Comment
Please, Sign In to add comment