#include #include #define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++) #define rep(i, n) rep2(i, 0, n) #define all(x) begin(x), end(x) #ifdef ENV_LOCAL #define dump \ if (1) cerr #else #define dump \ if (0) cerr #endif using namespace std; using namespace std::string_literals; using i32 = int32_t; using i64 = int64_t; using f64 = double; using f80 = long double; using vi32 = vector; using vi64 = vector; namespace std { bool operator<(const bitset<16>& lhs, const bitset<16>& rhs) { return lhs.to_ulong() < rhs.to_ulong(); } } // namespace std i64 permanent(const vector>& s) { i64 n = size(s); i64 ans = 0; rep(i, 1 << n) { i64 prod = 1; rep(j, n) { i64 sum = __builtin_popcount(i & s[j].to_ulong()); prod *= sum; } if (__builtin_popcount(i) % 2) prod *= -1; ans += prod; } if (n % 2) ans *= -1; return ans; } map>, vi64> cache; vi64 solve(const vector>& s) { i64 n = size(s); if (n == 1) { return {1}; } if (n == 2) { if (s[0][1]) { return {2, 0}; } else { return {0, 2}; } } if (cache.count(s)) { return cache.at(s); } vi64 ans(n); rep(i, 1 << n) { if (__builtin_popcount(i) != n / 2) continue; vi32 winner; vi32 loser; rep(j, n) { if ((i >> j) & 1) { winner.push_back(j); } else { loser.push_back(j); } } vector> mat(n / 2); rep(j, n / 2) rep(k, n / 2) { mat[j][k] = s[winner[j]][loser[k]]; } i64 cnt = permanent(mat); vector> ss(n / 2); rep(j, n / 2) rep(k, n / 2) { ss[j][k] = s[winner[j]][winner[k]]; } auto sans = solve(ss); cnt *= (1 << (n / 2)); rep(j, n / 2) { ans[winner[j]] += cnt * sans[j]; } } cache[s] = ans; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i64 n; cin >> n; vector> s(n); rep(i, n) rep(j, n) { i64 b; cin >> b; s[i][j] = b; } vi64 ans = solve(s); rep(i, n) { cout << ans[i] << endl; } return 0; }