/* -*- coding: utf-8 -*- * * 753.cc: No.753 最強王者決定戦 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int BN = 4; const int N = 1 << BN; const int NBITS = 1 << N; /* typedef */ typedef long long ll; typedef vector vi; /* global variables */ int bnums[NBITS]; vi nbbs[BN + 1], hbs[BN + 1]; int wls[N][N]; ll dp[NBITS][N]; /* subroutines */ inline void bits2v(int bits, vi &v) { v.clear(); for (int i = 0, bi = 1; bi <= bits; i++, bi <<= 1) if (bits & bi) v.push_back(i); } inline int v2hbits(vi &v, int hb) { int hbits = 0; for (int i = 0, bi = 1; i < v.size(); i++, bi <<= 1) if (hb & bi) hbits |= (1 << v[i]); return hbits; } /* main */ int main() { bnums[0] = 0; for (int bits = 1, msb = 1; bits < NBITS; bits++) { if ((msb << 1) <= bits) msb <<= 1; int bn = bnums[bits] = bnums[bits ^ msb] + 1; if (bnums[bn] == 1) { int k = 0; while (bn > 1) k++, bn >>= 1; nbbs[k].push_back(bits); } } //for (int i = 0; i <= BN; i++) printf("%d: %lu\n", i, nbbs[i].size()); for (int bn = 1; bn <= BN; bn++) { int n = 1 << bn, hn = n >> 1; int nbits = 1 << n; for (int bits = 0; bits < nbits; bits++) if (bnums[bits] == hn) hbs[bn].push_back(bits); } //for (int i = 0; i <= BN; i++) printf("%d: %lu\n", i, hbs[i].size()); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { scanf("%d", &wls[i][j]); if (i > j) wls[i][j] = -wls[j][i]; } for (int i = 0; i < N; i++) dp[1 << i][i] = 1; for (int bn = 1; bn <= BN; bn++) { vi &nbb = nbbs[bn], hbb = hbs[bn]; for (vi::iterator vit = nbb.begin(); vit != nbb.end(); vit++) { int &bits = *vit; vi bv; bits2v(bits, bv); for (vi::iterator hvit = hbb.begin(); hvit != hbb.end(); hvit++) { int hbits = v2hbits(bv, *hvit); int rbits = bits ^ hbits; for (int i = 0, bi = 1; i < N; i++, bi <<= 1) if (hbits & bi) for (int j = 0, bj = 1; j < N; j++, bj <<= 1) if (rbits & bj) { if (wls[i][j] > 0) dp[bits][i] += dp[hbits][i] * dp[rbits][j]; else dp[bits][j] += dp[hbits][i] * dp[rbits][j]; } } } } for (int i = 0; i < N; i++) printf("%lld\n", dp[NBITS - 1][i]); return 0; }