网站模板商城,网站空间数据库需要多大,九江网站建设服务,湖南智能网站建设Description 求有多少种长度为 n 的序列 A#xff0c;满足以下条件#xff1a;1 ~ n 这 n 个数在序列中各出现了一次若第 i 个数 A[i] 的值为 i#xff0c;则称 i 是稳定的。序列恰好有 m 个数是稳定的满足条件的序列可能很多#xff0c;序列数对 10^97 取模。Input 第一行…Description 求有多少种长度为 n 的序列 A满足以下条件 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多序列数对 10^97 取模。 Input 第一行一个数 T表示有 T 组数据。 接下来 T 行每行两个整数 n、m。 T500000n≤1000000m≤1000000 Output 输出 T 行每行一个数表示求出的序列数 Sample Input 5 1 0 1 1 5 2 100 50 10000 5000 Sample Output 0 1 20 578028887 60695423 组合错排 $ansC_{n}^{m}*D_n-m$ $D[n]n!(1-\frac{1}{1!}\frac{1}{2!}-.......(-1)^{n}\frac{1}{n!})$ 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includecmath6 using namespace std;7 typedef long long lol; 8 lol fac[1000001],inv[1000001],D[1000001];9 lol n,m,Mod1e97;
10 int main()
11 {lol i,T;
12 fac[0]1;
13 for (i1;i1000000;i)
14 fac[i]fac[i-1]*i%Mod;
15 inv[1]1;inv[0]1;
16 for (i2;i1000000;i)
17 inv[i](Mod-Mod/i)*inv[Mod%i]%Mod;
18 for (i2;i1000000;i)
19 inv[i]inv[i-1]*inv[i]%Mod;
20 D[0]1;
21 for (i1;i1000000;i)
22 if (i%20)
23 D[i](D[i-1]inv[i])%Mod;
24 else D[i](D[i-1]-inv[i]Mod)%Mod;
25 cinT;
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
