xdoj-1057(Lucas定理的证明及其模板）

Lucas定理的证明： 转自百度百科（感觉写的还不错）

首先你需要这个算式:

  

,其中f > 0&& f < p，然后

(1 + x) ⁿΞ(1 + x) ^sp+q Ξ( (1 + x)^p)^s· (1 + x) ^q Ξ(1 + x^p) ^s· (1 + x) ^q(mod p) 
　　

  

（modp)
所以得(1 + x) ^sp+q 

 

(mod p)
　　
我们求右边的

  

的系数为：

求左边的

  

为：

通过观察你会发现当且仅当i = t , j = r ,能够得到

  

的系数，即
　　

 

　
所以

得证。

 Lucas定理模板

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 typedef long long LL;

 const LL mod = ;

 LL fac[mod+];

 LL n,m;

 LL q_pow (LL x,LL k) {

     LL ans=;

     while (k) {

         if (k&) ans=ans*x%mod;

         k=k>>;

         x=x*x%mod;

     }

     return ans;

 }

 LL C (LL x,LL y) {

     if (y>x)  return ;// 重要

     LL t1=fac[x];

     LL t2=fac[x-y]*fac[y]%mod;

     return t1*q_pow(t2,mod-)%mod;

 }

 LL Lucas (LL x,LL y) {

     if (y==) return ;//递归出口

     return C (x%mod,y%mod)*Lucas (x/mod,y/mod)%mod;

 }

 int main ()

 {

     fac[]=;//一定不要忘了0

     for (int i=;i<=mod;i++)

         fac[i]=fac[i-]*i%mod;

     while (~scanf ("%lld %lld",&n,&m))

         printf ("%lld\n",Lucas(m+n-,n-));// （多重集合取组合数）

     return ;

 }

xdoj-1057(Lucas定理的证明及其模板）的相关教程结束。