[xdoj1158]阶乘求逆元(常用于求组合数)

http://acm.xidian.edu.cn/problem.php?id=1158

解题关键：此题注意将$\sum\limits_{i = 0}^x {C_x^iC_y^{i + k}}$转化为$C_{x + y}^{x + k}$

利用二项式定理，

一方面，

${(1 + a)^y}{(1 + \frac{1}{a})^x}$的${a^k}$项的系数，第一个二项式的${a^j}$的系数$C_y^j$，第二个二项式的${a^{ - i}}$系数为$C_x^i$，令$j - i = k$，$j = i + k$，即$\sum\limits_{i = 0}^x {C_x^iC_y^{i + k}}$

另一方面，

${(1 + a)^y}{(1 + \frac{1}{a})^x} = {(1 + a)^{x + y}}{a^{ - x}}$,此时${a^k}$项的系数为$C_{x + y}^{x + k}$，得证。

1、打表

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long  ll;

 const ll mod=1e9+;

 ll x,y,k;

 ll fac[],inv[];

 ll mod_pow(ll x,ll n,ll mod){

     ll res=;

     while(n){

         if(n&) res=res*x%mod;

         n>>=;

         x=x*x%mod;

     }

     return res;

 }

 ll Inv(ll x){

     return mod_pow(x,mod-,mod);

 }

 int main(){

     fac[]=;

     for(int i=;i<=;i++) fac[i]=fac[i-]*i%mod;//预处理一下，阶乘

     inv[]=mod_pow(fac[],mod-,mod);//Fac[N]^{MOD-2}

     for(int i=-;i>=;i--) inv[i]=inv[i+]*(i+)%mod;

     while(~scanf("%lld%lld%lld",&x,&y,&k)){

         if(y==k)  printf("1\n");

         else if(y<k)  printf("0\n");

       //  else   printf("%lld\n",fac[x+y]*inv(fac[x+k])%mod*inv(fac[y-k])%mod);

       else printf("%lld\n",(fac[x+y]%mod*inv[x+k]%mod*inv[y-k]%mod+mod)%mod);

     }

     return ;

 }

2、打表+逆元实现

为什么是$n{!^{\bmod - 2}}$

$n{!^{p - 2}}*n! = n{!^{p - 1}} = 1\bmod {\rm{ p;}}$(费马小定理)p为质数，此题中即为mod

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long  ll;

 const ll mod=1e9+;

 ll x,y,k;

 ll fac[],inv[];

 ll mod_pow(ll x,ll n,ll mod){

     ll res=;

     while(n){

         if(n&) res=res*x%mod;

         n>>=;

         x=x*x%mod;

     }

     return res;

 }

 ll Inv(ll x){

     return mod_pow(x,mod-,mod);

 }

 int main(){

     fac[]=;

     for(int i=;i<=;i++) fac[i]=fac[i-]*i%mod;//预处理一下，阶乘

     //inv[2000000]=mod_pow(fac[2000000],mod-2,mod);//Fac[N]^{MOD-2}

     //for(int i=2000000-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;

     while(~scanf("%lld%lld%lld",&x,&y,&k)){

         if(y==k)  printf("1\n");

         else if(y<k)  printf("0\n");

         else   printf("%lld\n",fac[x+y]*Inv(fac[x+k])%mod*Inv(fac[y-k])%mod);

       //else printf("%lld\n",(fac[x+y]%mod*inv[x+k]%mod*inv[y-k]%mod+mod)%mod);

     }

     return ;

 }

巴特西

[xdoj1158]阶乘求逆元(常用于求组合数)

最新文章

热门文章