- The problem of counting up a permutation of 21 things that satisfy certain conditions
- There are 21 different “usable ones” when deciding on one top and considering the remaining 20 permutations.
- Therefore, “usable things” is the domain of definition, and the number of things that satisfy the condition is the value.
- The “usable ones” are a subset of a set of at most 21, so 2^21, or approximately 10
- Enumerating subsets of a small set is fast using bitwise operations (not so much in raw Python).
- I guess some people call it bitDP.
- Raw Python was going to TLE, but with PyPy, AC python
def solve(N, data):
FULLBIT = (1 << N) - 1
memo = [-1] * (1 << N)
def f(cursor, available):
if cursor == N:
return 1
ret = memo[available]
if ret != -1:
return ret
ret = 0
j = 0
m = available
while m:
if m & 1:
# available woman
if data[cursor * N + j]:
# acceptable
ret += f(cursor + 1, available ^ (1 << j))
j += 1
m //= 2
ret %= MOD
memo[available] = ret
return ret
return f(0, FULLBIT)
https://atcoder.jp/contests/dp/submissions/15068618
This page is auto-translated from [/nishio/DP O](https://scrapbox.io/nishio/DP O) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.