bzoj4517: [Sdoi2016]排列计数--数学+拓展欧几里得

时间：2024-07-21 00:06:26

这道题是数学题，由题目可知，m个稳定数的取法是Cnm

然后剩下n-m本书，由于编号为i的书不能放在i位置，因此其方法数应由错排公式决定，即D(n-m)

　　错排公式：D[i]=(i-1)*(D[i-1]+D[i-2]);

所以根据乘法原理，答案就是Cnm * D(n-m)

接下来就是怎么求组合数的问题了

由于n≤1000000，因此只能用O(n)的算法求组合，这里用乘法逆元(inv[])来辅助求组合数

即 Cnm = n! / ((n-m)! * m!) = fac[n]*inv[n-m]*inv[m]

那么乘法逆元是什么呢？

假设一个数a，且a关于P的乘法逆元为x

那么 ax≡1 (mod P). 当且仅当 a 与 P 互质时x有解

简单的说，就是找一个数x，使得(x*a) mod P = 1

不难得出三者符合 ax+Py=1 (裴蜀定理), y可能是负数

因此我们可以用拓展欧几里得算出x的值，即为乘法逆元(用inv保存)

对于求出inv的过程，我们可以不必每次暴力求拓展欧几里得，可由下列递推式O(n)求出

　　inv[i]=(i+1)*inv[i+1]

而D数组只要O(n)推即可，其中D[0]=1, D[1]=0;

这道题让我明白。。组合数可以O(n)求得，了解了乘法逆元是什么，并且了解到世界上有个叫错排公式的神奇东西Orz

 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 #define LL long long
 using namespace std;
 ;
 ;
 int T,n,m;
 LL f[maxn],inv[maxn],d[maxn];

 inline void read(int &x){
     ;
     ') c=getchar();
     +c-, c=getchar();
 }

 inline LL ex_gcd(LL &x, LL &y, LL a, LL b){
     ){
         x=; y=;
         return a;
     }
     LL res=ex_gcd(x,y,b,a%b);
     LL t=x; x=y;
     y=t-a/b*x;
     return res;
 }

 inline LL calc(LL a, LL b){
     LL x,y;
     if (ex_gcd(x,y,a,b) == 1LL)
         return (x+b)%b;
 }

 int main(){
     read(T);
     f[]=;
     ; i<=maxn; i++) f[i]=f[i-] * (LL)i % MOD;
     inv[]=calc(f[],MOD);
     ; i>=; i--) inv[i]=inv[i+] * (LL)(i+) % MOD;
     d[]=; d[]=; d[]=;
     ; i<=maxn; i++) d[i]=(LL)(i-)*(d[i-]+d[i-]) % MOD;
     while (T--){
         read(n); read(m);
         LL ans=1LL;
         //printf("haha %lld %lld %lld %lld\n", f[n], inv[n-m], inv[m], d[n-m]);
         ans=ans*f[n]*inv[n-m] % MOD;
         ans=ans*inv[m] % MOD;
         ans=ans*d[n-m] % MOD;
         printf("%lld\n", ans);
     }
     ;
 }

相关文章