abc 041 D - 徒競走 (pyhton)

bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。
例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、
s & 1 == 0であれば、まだ１がゴールしていないので s から s | 1<<2 への遷移がとれる。

n,m = map(int,input().split())
c = [0]*n
for i in range(m):
  x,y = map(int,input().split())
  c[y-1] += 2**(x-1)
  
dp = [0]*(2**n)
dp[0] = 1

for s in range(2**n):
  for i in range(n):
    if s>>i & 1 == 0 and c[i] & s == 0:
      dp[s+2**i] += dp[s]

print(dp[-1])