4517: [Sdoi2016]排列计数
题意：多组询问，n的全排列中恰好m个不是错排的有多少个
容斥原理强行推♂倒她
$恰好m个不是错排 $
\[ =\ \ge m个不是错排 - \ge m+1个不是错排\binom{m+1}{m} - \ge m+2个不是错排\binom{m+2}{m}... \\
= \sum_{i=m}^n \binom{n}{i} (n-i)!\binom{i}{m} \\
= \frac{n!}{m!} \sum_{i=m}^n (-1)^{i-m} \frac{1}{(i-m)!}
\]
= \sum_{i=m}^n \binom{n}{i} (n-i)!\binom{i}{m} \\
= \frac{n!}{m!} \sum_{i=m}^n (-1)^{i-m} \frac{1}{(i-m)!}
\]
预处理阶乘逆元前缀和就可以\(O(1)\)回答了
其实错排公式也是这么推倒来的
PS:发现题解全都是用的错排公式，~~等出一道你们不知道公式的题你们再用啊~~
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
#define fir first
#define sec second
const int N=1e6+5, P=1e9+7;
inline int read() {
char c=getchar(); int x=0, f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, m;
ll inv[N], fac[N], facInv[N], s[N];
int main() {
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
inv[1]=1; fac[0]=facInv[0]=1;
s[0]=1;
for(int i=1; i<N; i++) {
if(i!=1) inv[i] = (P-P/i)*inv[P%i]%P;
fac[i] = fac[i-1]*i%P;
facInv[i] = facInv[i-1]*inv[i]%P;
s[i] = (s[i-1] + ((i&1) ? -facInv[i] : facInv[i]))%P;
}
int T=read();
while(T--) {
n=read(); m=read();
ll ans = fac[n]*facInv[m]%P * s[n-m]%P;
if(ans<0) ans+=P;
printf("%lld\n", ans);
}
}