hdu 3037 Saving Beans lucas定理-白红宇

hdu 3037 Saving Beans lucas定理

阅读量：5123 次

发布时间：2019-06-13

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

给n, m, p，求sigma(i = 0 to m) C(n-1+i, n-1)%p的值。

C(n-1, n-1)+C(n-1+1, n-1)+C(n-1+2, n-1)+.......

= C(n-1, 0)+C(n, 1)+C(n+1, 2)+....

= C(n, 0)+C(n, 1)+C(n+1, 2)+....

根据C(n, k) = C(n-1, k-1)+C(n-1, k) 可以推出来上面的式子最终合并为C(n+m, m)%p。

这个式子直接用lucas定理就可以了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#define pb(x) push_back(x)#define ll long long#define mk(x, y) make_pair(x, y)#define lson l, m, rt<<1#define mem(a) memset(a, 0, sizeof(a))#define rson m+1, r, rt<<1|1#define mem1(a) memset(a, -1, sizeof(a))#define mem2(a) memset(a, 0x3f, sizeof(a))#define rep(i, n, a) for(int i = a; i
                 
                   pll;const double PI = acos(-1.0);const double eps = 1e-8;ll mod;const int inf = 1061109567;const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };ll pow(ll a, ll b) { ll ret = 1; while(b) { if(b&1) { ret = ret*a%mod; } a = a*a%mod; b >>= 1; } return ret;}ll C(ll n, ll k) { if(n
                  
                   n-k) k = n-k; ll s1 = 1, s2 = 1; for(int i = 0; i
                   
                    >t; while(t--) { scanf("%I64d%I64d%I64d", &n, &m, &mod); ll ans = lucas(n+m, m); printf("%I64d\n", ans); } return 0;}