题意：多组询问，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)!} \]

预处理阶乘逆元前缀和就可以\(O(1)\)回答了

其实错排公式也是这么推倒来的

PS:发现题解全都是用的错排公式，等出一道你们不知道公式的题你们再用啊

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;#define fir first#define sec secondconst 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