题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

1 ~ n 这 n 个数在序列中各出现了一次

若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

满足条件的序列可能很多，序列数对 \(10^9+7\) 取模。

输入输出格式

输入格式：

第一行一个数 T，表示有 T 组数据。

接下来 T 行，每行两个整数 n、m。

输出格式：

输出 T 行，每行一个数，表示求出的序列数

输入输出样例

输入样例#1：

5

1 0

1 1

5 2

100 50

10000 5000

输出样例#1：

0

1

20

578028887

60695423

---

错排+组合数

显然答案是\(C(n,m) * f[n - m]\)

但是当时我把错排公式忘了

就现打表找了个好像不是很一样的递推式

$ if (i是偶数) f[i] = f[i - 1] * i + 1$

$ else f[i] = f[i - 1] * i - 1$

也过掉了这道题

#include
    
     #include
     
      #include
      
       #include
       
        # define int long longconst int M = 1000005 ;const int mod = 1e9 + 7 ;using namespace std ;inline int read() {    char c = getchar() ; int x = 0 , w = 1 ;    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }    return x*w ;}int n , m , Ans ;int f[M] , fac[M] ;void exgcd(int a , int b , int &x , int &y) {    if(b == 0) { x = 1 , y = 0 ; return ; }    exgcd(b , a % b , x , y) ;    int tmp = x ;    x = y ;    y = tmp - a / b * y ;}inline int inv(int a) {    int x , y ;    exgcd(a , mod , x , y) ;    return (x + mod) % mod ;}inline int C(int n , int m) {    if(m > n) return 0 ;    return (fac[n] * inv(fac[m] * fac[n - m]) + mod) % mod ;}# undef intint main() {# define int long long    f[0] = 1 ; f[1] = 0 ; fac[0] = 1 ; fac[1] = 1 ;    for(int i = 2 ; i <= 1000000 ; i ++) {        if(i % 2 == 0) f[i] = (f[i - 1] * i + 1 + mod) % mod ;        else f[i] = (f[i - 1] * i - 1 + mod) % mod ;          fac[i] = (fac[i - 1] * i) % mod ;    }    int T = read() ;    while(T --) {        n = read() ; m = read() ;        if(m > n) Ans = 0 ;        else Ans = (C(n , m) * f[n - m] + mod) % mod ;        printf("%lld\n",Ans) ;    }    return 0 ;}