Saving Beans HDU - 3037（盧卡斯定理）

題意：

他們想知道有多少種方法可以在n樹(shù)中保存不超過(guò)m個(gè)bean（它們是相同的）。

現(xiàn)在他們求助于你，你應(yīng)該給他們答案。 結(jié)果可能非常巨大; 你應(yīng)該輸出模p的結(jié)果，因?yàn)樗墒鬅o(wú)法識(shí)別大數(shù)。
1 <= n，m <= 1000000000,p保證是一個(gè)素?cái)?shù)

題解：

得到公式為：C(n+m,m)%p
利用盧卡斯定理優(yōu)化

代碼：

代碼中有兩種求逆元的方式

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n, m, p; ll Ext_gcd(ll a, ll b, ll &x, ll &y) {if (b == 0) { x = 1, y = 0; return a; }ll ret = Ext_gcd(b, a%b, y, x);y -= a / b * x;return ret; } ll Inv(ll a, int m) { ll d, x, y, t = (ll)m;d = Ext_gcd(a, t, x, y);if (d == 1) return (x%t + t) % t;return -1; } ll poww(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=(ans*a)%p;a=(a*a)%p;b>>=1;} return ans%p; } ll Cm(ll n, ll m, ll p) {ll a = 1, b = 1;if (m > n) return 0;while (m){a = (a*n) % p;b = (b*m) % p;m--;n--;} // return (ll)a*Inv(b, p) % p; return (ll)a*poww(b, p-2,p) % p; }int Lucas(ll n, ll m, ll p) {if (m == 0) return 1;return (ll)Cm(n%p, m%p, p)*(ll)Lucas(n / p, m / p, p) % p; }int main() {int T;cin >> T;while (T--){scanf("%lld%lld%lld", &n, &m, &p);printf("%d\n", Lucas(n + m, m, p));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Saving Beans HDU - 3037（卢卡斯定理）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。