Problem:

Playoff by all the teams

The Minato Mirai Football Association hosts its annual championship
as a single round-robin tournament,
in which each team plays a single match against all the others.

Unlike many other round-robin tournaments of football,
matches never result in a draw in this tournament.
When the regular time match is a tie,
overtime is played, and, when it is a tie again,
a penalty shootout is played to decide the winner.

If two or more teams won the most number of matches in the round-robin,
a playoff is conducted among them to decide the champion.

However, if the number of teams is an odd number,
it is possible that all the teams may have
the same number of wins and losses,
in which case all the teams participate in the playoff,
called a "full playoff" here.

Now, some of the tournament matches have already been played and we know
their results.
Whether or not a full playoff will be required may
depend on the results of the remaining matches.

Write a program that computes the number of win/loss combination patterns
of the remaining matches that lead to a full playoff.

The first datatset of the Sample Input represents the results of the
first three matches in a round-robin tournament of five teams, shown
in the following table.

In the table, gray cells indicate the matches not played yet.

Team1Team2Team3Team4Team5

Team1  lostlost

Team2 lost  

Team3 won  

Team4won   

Team5won   

In this case,
all the teams win the same number of matches
with only two win/loss combination patterns
of the remaining matches,
which lead to a full playoff,
as shown below.

In the two tables, the differences are indicated in light yellow.

Team1Team2Team3Team4Team5

Team1wonwonlostlost

Team2lostlostwonwon

Team3lostwonwonlost

Team4wonlostlostwon

Team5wonlostwonlost

Team1Team2Team3Team4Team5

Team1wonwonlostlost

Team2lostlostwonwon

Team3lostwonlostwon

Team4wonlostwonlost

Team5wonlostlostwon

Input

The input consists of multiple datasets, each in the following format.

n

m

x1 y1 

... 

xm ym 

n is an odd integer, 3, 5, 7, or 9,
indicating the number of teams participating in the tournament.

m is a positive integer less than n(n&#8722;1)/2,
which is the number of matches already finished.

xi and yi give
the result of the i-th match that has already taken place,
indicating that team xi defeated team
yi.
Each of xi and yi is an integer 1 through n
which indicates the team number. 
No team plays against itself, that is, for any i,
xi &#8800; yi.
The match result of the same team pair appears at most once.
That is, if i &#8800; j,
then
(xi,yi) &#8800;
(xj,yj) and
(xi,yi) &#8800;
(yj,xj) hold.

The end of the input is indicated by a line containing a zero.
The number of datasets does not exceed 100.

Output

For each dataset, output a single line containing one integer
which indicates the number of possible future win/loss patterns
that a full playoff will be required.

Sample Input

5
3
3 2
4 1
5 1
3
1
1 2
3
2
1 2
3 2
5
4
4 1
4 2
5 1
5 2
5
3
4 1
4 2
5 1
5
4
3 2
4 1
5 1
5 2
9
11
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
9 5
9
10
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
5
6
4 3
2 1
5 1
2 4
1 3
2 3
9
1
1 2
0

Output for the Sample Input

2
1
0
0
1
0
0
16
0
1615040



Sample input:
5
3
3 2
4 1
5 1
3
1
1 2
3
2
1 2
3 2
5
4
4 1
4 2
5 1
5 2
5
3
4 1
4 2
5 1
5
4
3 2
4 1
5 1
5 2
9
11
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
9 5
9
10
6 1
6 4
7 2
7 3
7 4
8 2
8 3
8 4
9 1
9 3
5
6
4 3
2 1
5 1
2 4
1 3
2 3
9
1
1 2
0


Sample output:
2
1
0
0
1
0
0
16
0
1615040

Submission status: Accepted

Solution code:
from itertools import combinations as comb

def main():
  while True:
    n = int(input())
    if n ==0:break
    m = int(input())
    result = [[None] * n for _ in range(n)]
    for _ in range(m):
      x, y = map(int, input().split())
      x -= 1
      y -= 1
      result[x][y] = True
      result[y][x] = False

    t_count = [lst.count(True) for lst in result]
    
    empty_index = [[] for _ in range(n)]
    empty_nums = [0] * n
    for i in range(n):
      for j in range(i + 1, n):
        if result[i][j] == None:
          empty_index[i].append(j)
          empty_nums[i] += 1

    limit = n // 2
    def search(x, t_count):
      if x == n:return 1
      choice_num = limit - t_count[x]
      if choice_num < 0 or choice_num > empty_nums[x]:return 0
      rest_num = empty_nums[x] - choice_num
      ret = 0
      for inds in comb(empty_index[x], rest_num):
        new_count = t_count[:]
        for ind in inds:
          new_count[ind] += 1
        ret += search(x + 1, new_count)
 
      return ret

    print(search(0, t_count))

main()

Submission status: Accepted

Solution code:
from itertools import combinations as comb

def main():
  while True:
    n = int(input())
    if n ==0:break
    m = int(input())
    result = [[None] * n for _ in range(n)]
    for _ in range(m):
      x, y = map(int, input().split())
      x -= 1
      y -= 1
      result[x][y] = True
      result[y][x] = False

    t_count = [lst.count(True) for lst in result]
    
    empty_index = [[] for _ in range(n)]
    empty_nums = [0] * n
    for i in range(n):
      for j in range(i + 1, n):
        if result[i][j] == None:
          empty_index[i].append(j)
          empty_nums[i] += 1
    
    memo = {}
    limit = n // 2
    def search(x, t_count):
      if (x, tuple(t_count)) in memo:return memo[(x, tuple(t_count))]
      if x == n:return 1
      choice_num = limit - t_count[x]
      if choice_num < 0 or choice_num > empty_nums[x]:return 0
      rest_num = empty_nums[x] - choice_num
      ret = 0
      for inds in comb(empty_index[x], rest_num):
        new_count = t_count[:]
        for ind in inds:
          new_count[ind] += 1
        ret += search(x + 1, new_count)
      memo[(x, tuple(t_count))] = ret
 
      return ret

    print(search(0, t_count))

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    rr = []

    def f():
        n = I()
        if n == 0:
            return

        m = I()
        xy = [LI_() for _ in range(m)]

        nn = n // 2
        aa = [[0] * n for _ in range(n)]
        wl = [[0] * 2 for _ in range(n)]
        for x, y in xy:
            aa[x][y] = aa[y][x] = 1
            wl[x][0] += 1
            wl[y][1] += 1

        for i in range(n):
            if wl[i][0] > nn or wl[i][1] > nn:
                rr.append(0)
                return True

        kh = []
        for x in range(n):
            for y in range(x+1, n):
                if aa[x][y] == 0:
                    kh.append((x,y))
        ks = len(kh)

        def ff(wl, i):
            if i == ks:
                return 1

            r = 0
            x,y = kh[i]
            if wl[x][0] < nn and wl[y][1] < nn:
                wl[x][0] += 1
                wl[y][1] += 1
                r += ff(wl, i+1)
                wl[x][0] -= 1
                wl[y][1] -= 1

            if wl[x][1] < nn and wl[y][0] < nn:
                wl[x][1] += 1
                wl[y][0] += 1
                r += ff(wl, i+1)
                wl[x][1] -= 1
                wl[y][0] -= 1

            return r

        rr.append(ff(wl, 0))

        return True

    while f():
        pass

    return JA(rr, "\n")


print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
def main(n):
    m = int(input())
    d = defaultdict(int)
    k = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            d[k] = (i, j)
            k += 1
    p = defaultdict(int)
    for i in range(m):
        x, y = map(int, input().split())
        p[(x, y)] = 1
        p[(y, x)] = -1
    ans = defaultdict(int)
    tmp = [0] * n
    ans[tuple(tmp)] = 1
    for i in range(k):
        nd = defaultdict(int)
        for key, value in ans.items():
            key = list(key)
            x, y = d[i]
            if p[(x, y)]:
                if p[(x, y)] == 1:
                    if key[x - 1] == n//2: continue
                    key[x - 1] += 1
                    nd[tuple(key)] += value
                else:
                    if key[y - 1] == n//2: continue
                    key[y - 1] += 1
                    nd[tuple(key)] += value
            else:
                    if key[y - 1] != n//2: 
                        key[y - 1] += 1
                        nd[tuple(key)] += value
                        key[y - 1] += -1
                    if key[x - 1] != n//2:
                        key[x - 1] += 1
                        nd[tuple(key)] += value
        ans = nd
    print(ans[tuple([n // 2] * n)])

if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

def dfs(idx,N,win_cnt,will_match):
    if(idx==N):
        #win_cntがすべて(N-1)/2なら1を返す
        return 1
    
    need_win = (N-1)//2 - win_cnt[idx] #引き分けにするための必要勝数
    need_lose = len(will_match[idx]) - need_win
    # print(need_win,need_lose,(len(will_match[idx]),win_cnt[idx]))
    if(need_win > len(will_match[idx]) or need_win < 0): # 残りの試合をどう戦っても、引き分けにならない
        return 0
    res = 0
    # print(idx,"が負ける必要がある",need_lose)
    for it in combinations(will_match[idx],need_lose): ##負け試合をピッタリ必要なだけ選ぶ
        tmp = win_cnt.copy() ##勝数をいじるので現状保存
        # print(idx,win_cnt)
        # print(list(it))
        for i in it:
            # print("i",i)
            tmp[i] += 1 ## idx番目のチームの負けなので相手チームの勝数を1増やす
        res += dfs(idx+1,N,tmp,will_match)
    
    return res
def solve(N):
    M=int(input())
    # print(N,M)
    XY = [[int(i)-1 for i in input().split()] for _ in range(M)]
    win_cnt = [0]*N #チームiが何回勝ったか

    match = [[-1]*N for _ in range(N)]
    for x,y in XY:
        match[x][y] = 1
        match[y][x] = 0
        win_cnt[x]+=1
        if(x>y):
            x,y = y,x
    will_match = [[] for _ in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            if(match[i][j]==-1): #戦ってない
                will_match[i].append(j)
    # print(*match,sep="\n")
    # print(win_cnt)
    # print(*will_match,sep="\n")
    ans = dfs(0,N,win_cnt,will_match)

    print(ans)
        


def main():
    input = sys.stdin.readline
    while True:
        N = int(input())
        if(not N):
            break
        solve(N)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

def dfs(d,s,l,v,dic):
    s_ = tuple(s)
    if dic[(d,s_)] != None:
        return dic[(d,s_)]
    if d == l:
        dic[(d,s_)] = 1
        for x in s:
            if x > (n>>1):
                dic[(d,s_)] = 0
                return 0
        return 1
    else:
        res = 0
        i,j = v[d]
        if s[i] < (n>>1):
            s[i] += 1
            res += dfs(d+1,s,l,v,dic)
            s[i] -= 1
        if s[j] < (n>>1):
            s[j] += 1
            res += dfs(d+1,s,l,v,dic)
            s[j] -= 1
        dic[(d,s_)] = res
        return res

def solve(n):
    dic = defaultdict(lambda : None)
    m = int(sys.stdin.readline())
    s = [0]*n
    f = [[1]*n for i in range(n)]
    for i in range(n):
        f[i][i] = 0
    for i in range(m):
        x,y = [int(x) for x in sys.stdin.readline().split()]
        x -= 1
        y -= 1
        s[x] += 1
        f[x][y] = 0
        f[y][x] = 0
    v = []
    for i in range(n):
        for j in range(i+1,n):
            if f[i][j]:
                v.append((i,j))
    l = len(v)
    print(dfs(0,s,l,v,dic))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)

Submission status: Accepted

Solution code:

# next_combination:
# given an integer cur, next_combination returns an integer nxt s.t.
#   nxt has the same number of 1s as cur
#   nxt is bigger than cur
#   no integer between cur and nxt has the same number of 1s as cur (and nxt)
def next_combination(cur):
    r1 = cur & -cur      # extracts the rightmost 1
    moved1 = cur + r1    # cancel the rightmost run of 1s and put 1 on its left
    rm1s = cur & ~moved1 # extracts the rightmost run of 1s
    reset = (rm1s // r1) >> 1 # the run of 1s moved to LSD and made its length decreased by 1
    nxt = moved1 | reset # new combination
    return nxt

# the next is i-th, with a[k] for k > i to win
# at most 4 wins for each: about 4^9 = 2^18 states?
while True:
    n=int(input())
    if n == 0: break
    
    m=int(input())
    # wons and loses so far
    wons=[ 0 for _ in range(n) ]
    loses=[ 0 for _ in range(n) ]
    for i in range(m):
        x,y=map(int,input().split())
        wons[x-1] |= (1<<(y-1))
        loses[y-1] |= (1<<(x-1))
	
    memo = tuple({} for _ in range(9) )
	
    
    def rec(i,ws):
        if i >= n: return 1
        if n - 1 - i < ws[i]: return 0
        if tuple(ws) in memo[i]:
            return memo[i][tuple(ws)]
        # possible assignments of ws[i] wins matching with the input
        k = ws[i]
        win = ((1<<k) - 1) << (i+1)   # beginning: k wins against i+1,...,i+k
        fin = win << (n-1-k-i)        # end: k wins against n-k+1...,n-1
        cnt = 0
        while True:
	    # print("win = {0}".format(bin(win)))
	    # print("fin = {0}".format(bin(fin)))
	    # consistency check with wons and loses 
            mask = (1<<n) - (1<<(i+1))  # i+1, ..., n-1
            won = wons[i]
            lose = loses[i]
            if (won & win) == (won & mask) and (lose & win) == 0:
                ok = True
                for j in range(i+1,n):
                    if (1<<j) & win == 0:
                        if ws[j] == 0: ok = False
                        ws[j] -= 1
                if ok: cnt += rec(i+1, ws)
                for j in range(i+1,n):
                    if (1<<j) & win == 0:
                        ws[j] += 1
            if win == fin: break
            win = next_combination(win)
        
        memo[i][tuple(ws)] = cnt
        return cnt
    
    ans=rec(0, [ n//2 for _ in range(n)] )	
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
while 1:
    N = int(input())
    if N == 0:
        break
    M = int(input())
    S = [0]*N
    A = [[None]*N for i in range(N)]
    for i in range(M):
        x, y = map(int, input().split()); x -= 1; y -= 1
        S[x] += 1
        A[x][y] = 1; A[y][x] = 0
    B = []
    for i in range(N):
        for j in range(i+1, N):
            if A[i][j] is None:
                B.append((i, j))
    L = len(B)
    memo = [{} for i in range(L)]
    def dfs(k, s):
        if L == k:
            return all(e <= N//2 for e in s)
        key = tuple(s)
        v = memo[k]
        if key in v:
            return v[key]
        res = 0
        i, j = B[k]
        if s[i]+1 <= N//2:
            s[i] += 1
            res += dfs(k+1, s)
            s[i] -= 1
        if s[j]+1 <= N//2:
            s[j] += 1
            res += dfs(k+1, s)
            s[j] -= 1
        v[key] = res
        return res
    print(dfs(0, S))