Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //{
- //#pragma gcc optimize("Ofast,unroll-loops")
- //#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
- //#define int long long
- //#define double long double
- #define MP make_pair
- #define F first
- #define S second
- #define MOD 1000000007
- #define INF 9000000000000000000LL
- //}
- int n, g[20];
- int fpow(int a, int b)
- {
- a %= MOD;
- int ret = 1;
- while (b)
- {
- if (b & 1)
- ret = (long long)ret * a % MOD;
- a = (long long)a * a % MOD;
- b >>= 1;
- }
- return ret;
- }
- int dfs(int now, int status)
- {
- if (now == 0)
- return !status;
- int ret = 0;
- for (int i = 0; i < n; i++)
- if ((status & (1 << i)) && (g[i] & (1 << now)))
- {
- int cnt = 0;
- for (int j = 0; j < n; j++)
- if ((g[i] & (1 << j)) && (status & (1 << j)))
- cnt++;
- ret = (ret + (long long)dfs(i, status ^ (1 << i)) * fpow(cnt + 1, MOD - 2) % MOD) % MOD;
- }
- return ret;
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cin >> n;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- {
- int t;
- cin >> t;
- if (t)
- g[i] |= (1 << j);
- }
- for (int i = 0; i < n; i++)
- {
- int ans = 0;
- for (int j = 0; j < (1 << n); j++)
- if ((j & g[i]) == g[i] && (j & 1))
- ans += dfs(i, j);
- cout << ans << " \n"[i == n - 1];
- }
- return 0;
- }
- // ***** ***** * * * ***** * * ***** *****
- // * * * * * * * ** * * * *
- // * * * ***** * * * * * * *****
- // * * * * * * * * ** * *
- // **** ***** * ***** ***** * * * *
- // * * *** * * **
- // * * * * * * **
- // * * * ***** ***** **
- // * * * * * * *
- // * * * * * * **
Advertisement
Add Comment
Please, Sign In to add comment