这周还是很忙，暂无进一步的学习记录。

这个人还没从计网实验中活过来

推荐这样一道题：https://ac.nowcoder.com/acm/contest/5633/D

题意是给出一个序列$a$，求多少组排列$p$满足对任意的$i$，有$p[i]\neq a[i]$。

我们容易知道当$a[i]=i$时求的就是错排数，如果是其他情况呢？

这里用到容斥原理+动态规划，状态的设置我觉得是极其巧妙的：

用$g(x)$代表选出$x$个取值，每个取值数字被不合法的$p[i]$所映射的情况数。

设$f(x)=x!$，那么$g(x)\times f(n-x)$为至少$x$个取值存在被不合法映射的方案数。

根据容斥原理答案为： $$ \sum_{i=0}^{n}(-1)^{i} * g(x) * f(n-x) $$ 设$h_i$表示不可以映射到$i$的$p$的位置个数，初始时： $$ g(0)=1, g(k)=0(k>1) $$ 然后定义$dp$状态为考虑前$i$个值，选出$x$个取值，每个取值数字被不合法的$p[i]$所映射的情况数。那么$g(x)=dp[n][x]$。而$dp[i][x]=dp[i-1][x]+dp[i-1][x-1]*h[i]$。因此可以求出所有$g(i)$最后统计答案。时间复杂度是$O(n^2)$的。

无