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 行，每行一個數，表示求出的序列數

Sample Input

5
1 0
1 1
5 2
100 50
10000 5000

Sample Output

0
1
20
578028887
60695423 組合+錯排 $ans=C_{n}^{m}*D_n-m$ $D[n]=n!(1-\frac{1}{1!}+\frac{1}{2!}-.......(-1)^{n}\frac{1}{n!})$ 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long lol; 8 lol fac[1000001],inv[1000001],D[1000001]; 9 lol n,m,Mod=1e9+7; 10 int main() 11 {lol i,T; 12 fac[0]=1; 13 for (i=1;i<=1000000;i++) 14 fac[i]=fac[i-1]*i%Mod; 15 inv[1]=1;inv[0]=1; 16 for (i=2;i<=1000000;i++) 17 inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod; 18 for (i=2;i<=1000000;i++) 19 inv[i]=inv[i-1]*inv[i]%Mod; 20 D[0]=1; 21 for (i=1;i<=1000000;i++) 22 if (i%2==0) 23 D[i]=(D[i-1]+inv[i])%Mod; 24 else D[i]=(D[i-1]-inv[i]+Mod)%Mod; 25 cin>>T; 26 while (T--) 27 { 28 scanf("%lld%lld",&n,&m); 29 printf("%lld\n",D[n-m]*fac[n]%Mod*inv[m]%Mod%Mod); 30 } 31 }

?

轉載于:https://www.cnblogs.com/Y-E-T-I/p/8457046.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[SDOI2016]排列计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。