#include #include #include #include using namespace std; using ll = long long int; const int N = 16; ll match[20][20], dp[1 << 16], frac[20]; int main() { frac[0] = 1; for(int i=1; i<=N; i++) { frac[i] = frac[i-1] * i; } for(int i=0; i> match[i][j]; if(i > j) match[i][j] = -match[j][i]; } } dp[(1<0; bit--) { if(dp[bit] == 0) continue; int popBit = __builtin_popcount(bit); for(int par=bit; par>0; par=(par-1)&bit) { int popPar = __builtin_popcount(par); if(popPar != popBit / 2) continue; // 勝者と敗者 vector winner, loser; for(int i=0; i> i & 1) winner.push_back(i); else if(bit >> i & 1) loser.push_back(i); } // 敗者の集合 int M = popPar; vector dp2(1 << M); dp2[0] = 1; for(int mask=0; mask<(1 << M); mask++) { int idx = __builtin_popcount(mask); // winner[idx] vs loser[jdx] for(int jdx=0; jdx> jdx & 1) continue; int nmask = mask | (1 << jdx); int A = winner[idx], B = loser[jdx]; if(match[A][B] == 1) { dp2[nmask] += dp2[mask]; } } } ll addVal = dp2[(1 << M) - 1] * dp[bit]; addVal *= (1 << M); // addVal *= frac[M]; dp[par] += addVal; } } /* for(int i=0; i<(1<(i).to_string() << "] = " << dp[i] << endl; } */ for(int i=0; i