大佬教程收集整理的这篇文章主要介绍了7.29 C幸运数字,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
@H_801_10@ |
时间限制 : - MS 空间限制 : - KB @H_675_23@ |
评测说明 : 1s,128m@H_675_23@ |
每个人都会有幸运数字,有种幸运数字是这样定义的:
如果 X 是幸运数字,则 X 在 m 进制下的表示为 x1x2...xk,一定有 x1<=x2<=...<=xk,其 中 k 可以表示 X 在 m 进制下的位数。
这样的数字可能有无穷多个的,但是如果是在 m 进制下位数不超过 n 的幸运数字,就 应该是有限个了,你能算出来吗?
这个答案可能很大,你只需要输出答案对一个数 p 取模的值即可。
共一行,三个正整数 n、m 和 p,保证 p 是质数。
共一行,表示答案对 p 取模的值。
4 3 23
15
4 10 10000079
715
前 20%的数据满足 n <= 18,m <= 10。
前 40%的数据满足 n <= 100,m <= 100。
前 60%的数据满足 n <= 1000,m <= 1000。
100%的数据满足 n <= 107,m <= 107,n + m <= p,p <= 10000079。
样例说明
样例 1 的 15 种方案如下:
0000,0001,0011,0111,1111,0002,0022,0222,2222,0012,0122,1222,1112,1122,1222
分析: 这题有一个很显然的DP 考试的时候由于纠结B题太久 没有打前缀和优化 掉了40分
// #include<bits/stdc++.h> @H_502_136@using @H_502_136@namespace std; @H_502_136@#define ll long long ll n,m,p; ll ksm(ll a,ll b,ll C) { ll ans=1; @H_502_136@while(b) { @H_502_136@if(b&1) ans=ans%P*(a%p); b>>=1; a=(a*a)%c; } @H_502_136@return ans%p; } ll c(@H_502_136@int n,@H_502_136@int m) { @H_502_136@if(n<m) @H_502_136@return 0; @H_502_136@if(n==m) @H_502_136@return 1; @H_502_136@if(n-m<m) m=n-@H_138_136@m; ll A=1,B=1; @H_502_136@for(@H_502_136@int i=0;i<m;i++) { A=(A%p)*(n-i)%p; B=(B%p)*(m-i)%p; } @H_502_136@return ksm(B,p-2,p)*A; } ll lucas(@H_502_136@int n,@H_502_136@int m,@H_502_136@int p) { @H_502_136@if(m==0) @H_502_136@return 1; @H_502_136@else @H_502_136@return lucas(n/p,m/p,p)%P*c(n%p,m%p)%p; } @H_502_136@int main() { // freopen("lucknum.in","r",stdin); // freopen("lucknum.out","w",stdout); scanf("%lld%lld%lld",&n,&m,&p); printf("%lld",lucas(n+m-1,n,p)%p); }
以上是大佬教程为你收集整理的7.29 C幸运数字全部内容,希望文章能够帮你解决7.29 C幸运数字所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。