十度网站建设,上海做网站 公司 哪家好,手机建网站怎么弄,网站设计侵权Saving Beans HDU - 3037#xff08;卢卡斯定理#xff09;
题意#xff1a;
他们想知道有多少种方法可以在n树中保存不超过m个bean#xff08;它们是相同的#xff09;。
现在他们求助于你#xff0c;你应该给他们答案。 结果可能非常巨大; 你应该输出模p的结果…Saving Beans HDU - 3037卢卡斯定理
题意
他们想知道有多少种方法可以在n树中保存不超过m个bean它们是相同的。
现在他们求助于你你应该给他们答案。 结果可能非常巨大; 你应该输出模p的结果因为松鼠无法识别大数。 1 nm 1000000000,p保证是一个素数
题解
得到公式为C(nm,m)%p 利用卢卡斯定理优化
代码
代码中有两种求逆元的方式
#includebits/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 ans1;while(b){if(b1)ans(ans*a)%p;a(a*a)%p;b1;} 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;
}
