【ACWing】230. 排列计数

题目地址：

https://www.acwing.com/problem/content/description/232/

求有多少种长度为$n$的序列$A$，满足以下条件：$1\sim n$这$n$个数在序列中各出现了一次。若第$i$个数$A[i]$的值为$i$，则称$i$是稳定的，序列恰好有$m$个数是稳定的。由于满足条件的序列可能很多，所以请你将序列数对$10^9+7$取模后输出。

输入格式：
第一行一个数$T$，表示有$T$组数据。
接下来$T$行，每行两个整数$n$、$m$。

输出格式：
输出$T$行，每行一个整数，表示求出的序列数对$10^9+7$取模后的值。

数据范围：
$T\le 500000,n\le 1000000,m\le 1000000$

首先，$k$个数的错排问题的解$f[k]$满足$f[k]=(k-1)(f[k-1]+f[k-2]),f[1]=0,f[2]=1$。参考https://blog.csdn.net/qq_46105170/article/details/125235949。那么本题可以分步骤，先取$m$个数，方案为$\left(\genfrac{}{}{0ex}{}{n}{m}\right)$个，剩下的$n-m$个数做错排即可。所以答案就是$$\left(\genfrac{}{}{0ex}{}{n}{m}\right)f[n-m]$$$f$值可以打个表，阶乘的值也可以打个表。由于$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}$，而$p=10^9+7$是个素数，从而$a$模$p$的逆元可以用费马小定理和快速幂来做。费马小定理为，若$p$为素数，$(a,p)=1$，则$a^{p-1}\equiv a{a}^{p-2}\equiv 1(\mathrm{mod}p)$，从而$a$的逆元为$a^{p-2}$。逆元可以用记忆化避免重复计算。代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10, P = 1e9 + 7;
long fac[N], f[N], inv[N];
int n, m;

long fast_pow(long x, int p) {
    
  long res = 1;
  while (p) {
    
    if (p & 1) res = res * x % P;
    x = x * x % P;
    p >>= 1;
  }
  return res;
}

long inverse(int i) {
    
  if (~inv[i]) return inv[i];
  return inv[i] = fast_pow(fac[i], P - 2);
}

long comb(int n, int m) {
    
  return fac[n] * inverse(m) % P * inverse(n - m) % P;
}

int main() {
    
  memset(inv, -1, sizeof inv);
  f[0] = 1, f[1] = 0;
  fac[0] = fac[1] = 1;
  for (int i = 2; i < N; i++) {
    
    f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % P;
    fac[i] = fac[i - 1] * i % P;
  }

  int T;
  scanf("%d", &T);
  while (T--) {
    
    scanf("%d%d", &n, &m);
    printf("%ld\n", comb(n, m) * f[n - m] % P);
  }
}

预处理时间复杂度$O(N)$（$N$为$n$数据范围），每次询问时间$O(\log P)$，$P=10^9+7$。