DP O

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^7

Enumerating subsets of a small set is fast using bitwise operations (not so much in raw Python).

Raw Python was going to TLE, but with PyPy, AC

code:python

def solve(N, data):

FULLBIT = (1 << N) - 1

def f(cursor, available):

if cursor == N:

return 1

if ret != -1:

return ret

ret = 0

j = 0

m = available

while m:

if m & 1:

# available woman

# acceptable

ret += f(cursor + 1, available ^ (1 << j))

j += 1

m //= 2

ret %= MOD

return ret

return f(0, FULLBIT)

---