容斥或者错排

guanjinquan · 2021-12-21 13:39:20 · 题解

该题可以使用两个方法通过此题。

第一个是错位排序，错位排列是指a_i \neq i的排列。但是实际上这个公式可以换成 a_i \neq b_i (其中b_i是一个排列)。

呃，python的话可以不写高精。

第二个做法是全排列+容斥。如果只是行列不同的问题，那么直接全排列就行了。但是多了n个限制条件，这就需要容斥原理了。

就是枚举i个棋子放在障碍物上，然后其它棋子变成一个n-i的全排列问题。

反正容斥的套路大概就是这样。 贴一个容斥的代码。

f = [0 for _ in range(1000)]
C = [[0 for j in range(1000)] for _ in range(1000)]
f[0] = 1
for i in range(1,222):
    f[i] = f[i - 1] * i

C[0][0] = 1
for i in range(1,222):
    C[i][i] = C[i][0] = 1
    for j in range(1,i):
        C[i][j] = C[i-1][j] + C[i-1][j-1]

ans, n = 0, int(input())
for i in range(n):
    input()
for i in range(0, n+1):
    ans += (-1 if i % 2 > 0 else 1) * C[n][i] * f[n - i]
print(ans)