简单来说，错排问题就是问有多少个长度为$n$的排列$p$，使得对于所有的$i\in [1,n]$都有$i \neq p_i$。
错排的一个递推式就是$f(n)=n(f(n-1)+f(n-2))$
这个递推式复杂度显然是线性的。
关于这个递推式的推导请自行百度。这里不再赘述。
第一次看到错排问题的时候，并没有推导出上面的递推式。而是用了一种容斥的方法。自认为更加简单易懂吧。
既然是每个数字都不能放在对应的位置。那么按照容斥的一般套路，我们强制有$i$个数字放在了对应位置。其他数字不管他。显然这$i$个数字有$C(_n^i)$种方案。其他数字有$(n-i)!$种排列方式。
所以式子就很显然了:
\[f(n)=\sum\limits_{i=0}^n(-1)^iC(_n^i)(n-i)! \\ =\sum\limits_{i=0}^n(-1)^i\frac{n!}{i!}\]复杂度同样也是线性的。
其实可以发现，用容斥继续推下去的话，依然可以推出上面的递推式。所以这两种解法本质上是等价的。
题目链接problem给出一个括号序列，要求删除一些括号使得剩下的括号序列是个匹配的括号序列，且改括号序列左边全部为左括号，右边全部为右括号。solution考虑枚举左右括号交界的位置$x$，为了避免重复计算，强制要求$x$左边的第一个左括号必选。然后枚举$x$的时候只枚举左括号的位置。然后枚举括号序列的长度。假设长度为$2i$，那么左右括号就分别有$i$个，假设左边有$n$个左括号，右边有$m$个右括号。那么该位置的答案就是$\sum\limits_{i=1}^{min(n,m)}C_{...…
题目链接problem有$n$个人，每个人家有一只猫。每个人都认识一些猫(其中肯定包括自己家的猫)。选出$j$个人和$k$只猫$j,k\ge 1$。使得$j+k=n$且选出的人和猫都互不认识。solution一个显然但是重要的推论是: 每个人家都必须去一个人或者一只猫。这样我们只需要枚举第一个人家去的是人还是猫，就可以根据他们之间的关系推出其他的人家是人还是猫。当无论第一家选择人还是选择猫，都会导致去$n$只猫或者$n$个人时无解。code#include<cstdio>#i...…
