7.29 C幸运数字

发布时间：2020-12-16 10:48:28 所属栏目：百科来源：网络整理

导读：? 时间限制 : - MS?? 空间限制 : - KB 评测说明 : 1s,128m 问题描述每个人都会有幸运数字，有种幸运数字是这样定义的：如果 X 是幸运数字，则 X 在 m 进制下的表示为 x1x2...xk，一定有 x1=x2=...=xk，其中 k 可以表示 X 在 m 进制下的位数。这样的数字

时间限制 : - MS?? 空间限制 : - KB

评测说明 : 1s,128m

问题描述

每个人都会有幸运数字，有种幸运数字是这样定义的：
如果 X 是幸运数字，则 X 在 m 进制下的表示为 x1x2...xk，一定有 x1<=x2<=...<=xk，其中 k 可以表示 X 在 m 进制下的位数。
这样的数字可能有无穷多个的，但是如果是在 m 进制下位数不超过 n 的幸运数字，就应该是有限个了，你能算出来吗？
这个答案可能很大，你只需要输出答案对一个数 p 取模的值即可。

输入格式

共一行，三个正整数 n、m 和 p，保证 p 是质数。

输出格式

共一行，表示答案对 p 取模的值。

样例输入 1

4?3?23?

样例输出 1

样例输入 2

4?10?10000079?

样例输出 2

715

提示

前 20%的数据满足 n <= 18,m <= 10。
前 40%的数据满足 n <= 100,m <= 100。
前 60%的数据满足 n <= 1000,m <= 1000。
100%的数据满足 n <= 10^{7,m <= 10}7,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分

20%搜索即可50%DP,f[i][j]表示以 j 结尾，长度为 i 的数字的个数。则 f[i][j]=sum{f[i-1][k]},k<=j,f[1][j]=1，复杂度 O(n^3)80%注意到前面求 f[i][j]时有求前缀和，那么用 g[i][j]表示 f[i][1]到 f[i][j]的和，则 dp 可以优化到O(nm)100%80 分的算法中，f[i][j]=g[i-1][j]，也可以写成 g[i][j]-g[i][j-1]=g[i-1][j]，即 g[i][j]=g[i-1][j]+g[i][j-1]，这类似于一个杨辉三角形，并且发现边界 g[1][i]=i 恰好是杨辉三角形去掉最外层 1 的一边，因此可以使用组合数的方法进行直接计算 g[i][j]的值：g[i][j]=c(i,i+j-1);最终答案：ans=sum(g[i][m-1]),1<=i<=n根据 g[i][j]=g[i-1][j]+g[i][j-1]化简可以得到ans=g[n][m]=c(n,n+m-1)

至于g[i][[j] 为啥会得到C(i,i+j-1)? 我只能说靠经验

然后分享一波 lucas定理板子

C(N,M)=C(N%P,M%P)*lucas(N/P,M/P);

虽然说n+m<=p 用不到lucas

code：

//
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,m,p;
ll ksm(ll a,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans%p*(a%p);
        b>>=1;
        a=(a*a)%c;
    }
    return ans%p;
}
ll c(int n,int m)
{
    if(n<m) return 0;
    if(n==m) return 1;
    if(n-m<m) m=n-m;
    ll A=1,B=1;
    for(int i=0;i<m;i++)
    {
        A=(A%p)*(n-i)%p;
        B=(B%p)*(m-i)%p;
    }
    return ksm(B,p-2,p)*A;
}

ll lucas(int n,int m,int p)
{
    if(m==0) return 1;
    else
    return lucas(n/p,m/p,p)%p*c(n%p,m%p)%p; 
}
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);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!