Saving Beans http://acm.hdu.edu.cn/showproblem.php?pid=3037

#include<cstdio>
typedef __int64 LL;
const int M=;
class LUCAS { //lucas Find the combination number C(n,k)%p
LL F[M];
LL inv(LL a,LL mod) {
if(a==) return ;
return inv(mod%a,mod)*(mod-mod/a)%mod;
}
void init(LL p) {
F[]=;
for(int i=; i<=p; i++) {
F[i]=F[i-]*i%p;
}
}
LL Lucas(LL n,LL k,LL p) {
LL ans=;
while(n&&k) {
LL a=n%p;
LL b=k%p;
if(a<b) return ;
ans=ans*F[a]%p*inv(F[b]*F[a-b]%p,p)%p;
n/=p;
k/=p;
}
return ans;
}
public:
LL solve(LL n,LL k,LL p){
init(p);
return Lucas(n,k,p);
}
}gx;
int main() {
int t,n,m,p;
while(~scanf("%d",&t)) {
while(t--) {
scanf("%d%d%d",&n,&m,&p);
printf("%d\n",(int)gx.solve(n+m,n,p));
}
}
return ;
}

DP? http://acm.hdu.edu.cn/showproblem.php?pid=3944

#include<cstdio>
#include<cstring>
#include<vector>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef __int64 LL;
const int M=;
class LUCASM { // More suitable n,k<=10^9,p<=10^4 The situation of
int flag[M*],prime[],pcnt;
vector<int> rev[M],fac[M];
int quickpow(int a,int b,int c) { // Fast exponentiation (a^b)%c
int ret=%c;
for(; b; a=a*a%c,b>>=) {
if(b&) {
ret=ret*a%c;
}
}
return ret;
}
public:
void init() {// Just initialize once
pcnt=;
mt(flag,-);
for(int i=; i<=; i++) {
if(flag[i]) {
prime[pcnt++]=i;
rev[i].clear();
fac[i].clear();
}
for(int j=; j<pcnt&&prime[j]<=/i; j++) {
flag[i*prime[j]]=;
if(!(i%prime[j])) break;
}
}
for(int i=; i<pcnt; i++) {
int tnum=;
rev[prime[i]].push_back();
fac[prime[i]].push_back();
for (int j=; j<prime[i]; j++) {
tnum=(tnum*j)%prime[i];
int now=quickpow(tnum,prime[i]-,prime[i]);
fac[prime[i]].push_back(tnum);
rev[prime[i]].push_back(now);
}
}
}
int lucas(int n,int k,int p) {
int ret=;
while (n && k) {
int num1=n%p;
int num2=k%p;
n/=p;
k/=p;
if (num1<num2) return ;
int num=(fac[p][num1]*rev[p][num2])%p;// Calculation c(num1,num2)%p
num=(num*rev[p][num1-num2])%p;
ret=(ret*num)%p;
}
return ret;
}
} gx;
int main() {
int n,k,p,cas=;
gx.init();
while(~scanf("%d%d%d",&n,&k,&p)) {
printf("Case #%d: ",cas++);
if(k>n/) k=n-k;
int o=gx.lucas(n+,k,p);
printf("%d\n",(n-k+o)%p);
}
return ;
}

end

lucas Find the combination number C(n,k)%p More articles about

1. 1067 - Combinations---LightOj（Lucas Find the combination number ）

Topic link :http://lightoj.com/volume_showproblem.php?problem=1067 Template seeking C(n,m)%p, Lucas Templates ; #include <iostr ...

2. Find the combination number C++ Program

One Recursive combination number Let the function be void    comb(int m,int k) To find out from natural numbers 1.2.... .m Take whatever you like k All combinations of numbers . analysis : When the first number of the combination is selected , The following figures are from the rest of m-1 In number ...

3. HDU 5698—— Instant movement ——————【 The inverse element is used to find the combination number 】

Instant movement Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submis ...

4. mathematics -- number theory --HDU 4675 GCD of Sequence( Mobius inversion + Lucas theorem for combinatorial numbers + Multiplicative inverse element + Fast power modulus ）

Let's start with some knowledge : Mobius inversion Lucas theorem for combinatorial numbers Multiplicative inverse element Fast power modulus GCD of Sequence Alice is playing a game with Bob. Alice shows N i ...

5. URAL 1994 The Emperor&#39;s plan Find the combination number Large numbers use log+exp Handle

URAL 1994 The Emperor's plan Find the combination number Large numbers use log #include<functional> #include<algorithm> #inclu ...

6. HDU 5852 Intersection is not allowed!（LGV Theorem determinant for combination number ） Answer key

The question : Yes K A chess piece in a size of N×N The chessboard of . In limine , They're all at the top of the board , They start at  (1,a1),(1,a2),...,(1,ak) , Their destination is  (n,b1),(n,b2),...,(n,b ...

7. Codeforces Round #361 (Div. 2) E. Mike and Geometry Problem 【 The inverse element is used to find the combination number &amp;&amp; discretization 】

Random door :http://codeforces.com/contest/689/problem/E E. Mike and Geometry Problem time limit per test 3 s ...

8. 51nod1119( Division modulus / Fermat's small theorem for combinatorial numbers )

Topic link :https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1119 The question : Chinese question - Ideas : This is a big problem. Direct violence is definitely not ...

9. [2011 Shandong ACM Provincial competition ] Binomial Coeffcients（ Find the combination number ）

Random recommendation

1. Android calls Baidu map api error mcode Parameter does not exist

My own cell phone app Baidu map is used in the website sdk, Hope to get the coordinates according to the mobile phone to reverse to Baidu map coordinates . according to api The document is spelled url, Because it's mobile , It's about adding mcode Parameters , And then my url It looks like : http://a ...

2. SQL SERVER Operational Schedules elementary analysis

SQL SERVER The plan of the assignment (Schedules), If you haven't studied or applied some complicated plans (Schedules), So you think SQL SERVER The plan of the assignment (Schedules) Very easy to use , No questions ...

3. mysql Use in where 1=1 and 0=1 The role of

operation mysql When , Regular use where Statement to query . When where When the statement doesn't exist , Always add a where 1=1 where 1=1; This condition is always True, Under the condition of indefinite quantity inquiry ,1=1 can ...

4. awk My graffiti

awk Too cattle , broad and profound , I can't understand , You don't have to , Forget again . So it took a day , I summed up the foundation , Look it up in the dictionary ( Easy to forget ). There is something wrong , I forgot to point out that . [ganzl@cmdb ~]\$ more /etc/passwd ...

5. WWDC2014 And iOS Using dynamic libraries framework【 turn 】

from:http://www.cocoachina.com/industry/20140613/8810.html JUN 12TH, 2014 Apple's openness WWDC2014 Posted on Xcode6 ...

6. Intelli IDEA ultimate Cracking method

Today I installed a Intelli IDEA,ultimate edition , Using online methods to crack , Crack method reference website   http://appcode.aliapp.com/idea.jsp Intelli IDEA There is one vi ...

7. Cocos2d Learning material recommendation

I finally found an introduction cocos2d Good books , Be careful , No cocos2d-x! This book is called <cocos2d Authoritative guide > pricing 99 element , TaoBao 60 multivariate , In detail cocos2d All aspects of ! But you need to have oc ...

8. APIO dispatching

Title Description In a ninja gang , Some ninjas were chosen to be sent to customers , And then get paid for what you do . In this gang , There's a ninja called  Master. except  Master outside , Every Ninja has and has only one superior . For the sake of secrecy , At the same time ...

9. hdu 2296 aC automata +dp( Get the most valuable string )

Ring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submis ...

10. Behavior We couldn't find Expression.Interactions To solve the problem

For example, use Behavior Example , Need to refer to :Microsoft.Expression.Interactions.dll. <Window x:Class="VisualStudioB ...