ZOJ 3557-How Many Sets II(Lucas定理+插板法求组合数)-白红宇

ZOJ 3557-How Many Sets II(Lucas定理+插板法求组合数)

阅读量：2029 次

发布时间：2019-04-28

本文共 1003 字，大约阅读时间需要 3 分钟。

题目地址：

题意：给一个集合，一共n个元素，从中选取m个元素，满足选出的元素中没有相邻的元素，一共有多少种选法(结果对p取模1 <= p <= 10^9)

思路：用插板法求出组合数。既然是从n个数中选择m个数，那么剩下的数为n-m，那么可以产生n-m+1个空，这道题就变成了把m个数插到这n-m+1个空中有多少种方法，即C(n-m+1,m)%p。然后就Lucas定理上去乱搞。因为这道题的p较大，所以不能预处理。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;LL n,m,p;LL modxp(LL a,LL b){ LL res=1; while(b>0){ if(b&1) res=res*a%p; b=b>>1; a=a*a%p; } return res;}LL C(LL n,LL m){ if(m>n) return 0; if(m==n) return 1; LL ans=1; for(int i=1;i<=m;i++){ LL a=(n+i-m)%p; LL b=i%p; ans=ans*(a*modxp(b,p-2)%p)%p; } return ans;}LL Lucas(LL n,LL m){ if(m==0) return 1; return C(n%p,m%p)*Lucas(n/p,m/p);}int main(){ while(~scanf("%lld %lld %lld",&n,&m,&p)){ printf("%lld\n",Lucas(n-m+1,m)%p); } return 0;}

转载地址：http://acsaf.baihongyu.com/

你可能感兴趣的文章

高效能人士的七个习惯——由内而外全面造就自己