首页 > 代码库 > HDU 3037 Saving Beans (数论，Lucas定理)
HDU 3037 Saving Beans (数论，Lucas定理)
题意：问用不超过 m 颗种子放到 n 棵树中，有多少种方法。
析：题意可以转化为 x1 + x2 + .. + xn = m，有多少种解，然后运用组合的知识就能得到答案就是 C(n+m, m)。
然后就求这个值，直接求肯定不好求，所以我们可以运用Lucas定理，来分解这个组合数，也就是Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p)。
然后再根据费马小定理就能做了。
代码如下：
第一种：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <unordered_map>
//#include <tr1/unordered_map>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10005;
const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int hr[]= {-2, -2, -1, -1, 1, 1, 2, 2};
const int hc[]= {-1, 1, -2, 2, -2, 2, -1, 1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
LL exgcd(LL a,LL b,LL &x,LL &y){LL d = a;if(b!=0){d=exgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1;y=0;}return d;}
LL mod_inverse(LL a,LL m){LL x,y;exgcd(a,m,x,y);return (m+x%m)%m; }
inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
LL fact[100005];
LL mod_fact(LL n, LL p, LL &e){
e = 0;
if(!n) return 1;
LL res = mod_fact(n / p, p, e);
e += n / p;
if(n / p % 2 != 0) return res * (p - fact[n%p]) % p;
return res * fact[n%p] % p;
}
LL mod_comb(LL n, LL k, LL p){
if(n < 0 || k < 0 || n < k) return 0;
LL e1, e2, e3;
LL a1 = mod_fact(n, p, e1);
LL a2 = mod_fact(k, p, e2);
LL a3 = mod_fact(n-k, p, e3);
if(e1 > e2+e3) return 0;
return a1 * mod_inverse(a2*a3%p, p) % p;
}
int main(){
fact[0] = 1;
int T; cin >> T;
while(T--){
LL p, m, n;
scanf("%I64d %I64d %I64d", &n, &m, &p);
for(int i = 1; i < p; ++i) fact[i] = fact[i-1] * (LL)i % p;
printf("%I64d\n", mod_comb(n+m, m, p));
}
return 0;
}
第二种：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <unordered_map>
//#include <tr1/unordered_map>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10005;
const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int hr[]= {-2, -2, -1, -1, 1, 1, 2, 2};
const int hc[]= {-1, 1, -2, 2, -2, 2, -1, 1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
LL fact[100005];
LL p;
LL quick_pow(LL a, LL b){
LL ans = 1LL;
a %= p;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
LL C(LL n, LL m){
if(n < m) return 0;
return fact[n] * quick_pow(fact[m]*fact[n-m], p-2) % p;
}
LL lucas(LL n, LL m){
if(!m) return 1LL;
return C(n%p, m%p) * lucas(n/p, m/p) % p;
}
int main(){
fact[0] = 1;
int T; cin >> T;
while(T--){
LL m, n;
scanf("%I64d %I64d %I64d", &n, &m, &p);
for(int i = 1; i < p; ++i) fact[i] = fact[i-1] * (LL)i % p;
printf("%I64d\n", lucas(n+m, m));
}
return 0;
}
第三种：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <unordered_map>
//#include <tr1/unordered_map>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10005;
const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int hr[]= {-2, -2, -1, -1, 1, 1, 2, 2};
const int hc[]= {-1, 1, -2, 2, -2, 2, -1, 1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
LL p;
LL quick_pow(LL a, LL b){
LL ans = 1LL;
a %= p;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
LL C(LL n, LL m){
if(n < m) return 0;
LL a = 1, b = 1;
while(m){
a = a * n % p;
b = b * m % p;
--m; --n;
}
return a * quick_pow(b, p-2) % p;
}
LL lucas(LL n, LL m){
if(!m) return 1LL;
return C(n%p, m%p) * lucas(n/p, m/p) % p;
}
int main(){
int T; cin >> T;
while(T--){
LL m, n;
scanf("%I64d %I64d %I64d", &n, &m, &p);
printf("%I64d\n", lucas(n+m, m));
}
return 0;
}
HDU 3037 Saving Beans (数论，Lucas定理)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。