BZOJ4517 - Click Here
Description
求有多少种长度为 n 的序列 A，满足以下条件：
1~n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。
Input
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
T=500000，n≤1000000，m≤1000000
Output
输出 T 行，每行一个数，表示求出的序列数
Solutions
呜呜呜，退役生活好难受啊，文化课完全听不进去(所以我用物理课来推错排问题)
我们考虑弱化版问题：稳定的位置是给出的，且这个位置集合为$S$。
设$f(S)$表示$S$集合的位置是稳定的方案，$g(S)$表示仅有$S$集合的位置是稳定的方案。
显然有$f(S)=\sum_{S \subseteq S’} g(S’)=(n-\mid S \mid)!$，容斥一下有$g(S)=\sum_{S \subseteq S’} (-1)^{\mid S’ \mid - \mid S \mid}f(S’)$
把$f(S’)=(n- \mid S’ \mid)!$带入得到$g(S)=\sum_{S \subseteq S’} (-1)^{\mid S’ \mid - \mid S \mid}(n - \mid S’ \mid)!$
将变量改为数值，即用$g(\mid S \mid)$取代上诉的$g(S)$，则可得到$g(x)=\sum_{x \leq y \leq n} (-1)^{(y-x)}(n-y)!\binom{n-x}{y-x}$
回到本题，稳定位置的集合未给出，但是给出了集合大小。同时考虑到对于不同的大小相同的集合，其方案互相独立。因此可以直接枚举集合，再套用上诉式子，即答案为$\binom{n}{m}g(m)$
化简一下有，$ans=\frac{n!}{m!}\sum_{0 \leq k \leq n-m} \frac{(-1)^k}{k!}$
把阶乘之类的预处理一下，就能$O(1)$询问啦。还是挺好推的~
CODE
CODE - Click Here