2019西北工业大学程序设计创新实践基地春季选拔赛 D(卢卡斯定理)

链接：https://ac.nowcoder.com/acm/contest/553/D
来源：牛客网

Chino with Equation

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Chino的数学很差，因此Cocoa非常担心。今天，Cocoa要教Chino解不定方程。
众所周知，不定方程的解有0个或者若干个。
给出方程:

Cocoa想知道这个不定方程的正整数解和非负整数解各有几个。
题目对Chino来说太难啦，你能帮一帮Chino吗？

输入描述:

两个正整数m, n

输出描述:

题目要求的答案，即正整数解的个数和非负整数解的个数 。由于答案可能会很大，你只需要输出答案 mod(10 9+ 7) 即可。

示例1

输入

复制

4 7

输出

复制

20 120

解题思路：
组合数：
1.n,m比较小时：C(n,m)=C(n-1,m)+C(n-1,m-1);
2.卢卡斯定理：n,m比较大时：C(n,m)%mod=C(n%mod,m%mod)*C(n/mod,m/mod)%mod;

第一种情况：将n拆分成m个正整数的和，可以认为将n个小球放入m个盒子，每个盒子都不可为空，可以直接用隔板法，n个小球有n-1的空隙，我们只要在n-1个空隙中选择m-1个空隙放入隔板即可，答案为C(n-1,m-1)
第二种情况：将n拆分成m个非负整数的和，可以认为将n个小球放入m个盒子，但是有的盒子可以为空，不能直接使用隔板法，可以假设我们从外面拿了m个小球，以保证每个盒子至少有一个小球，然后继续又使用隔板法，n+m个小球有n+m-1个间隙，选择其中的m-1个空隙放入隔板就可以了，放完隔板后，每部分取走一个小球即为每个盒子球的个数，方案总数为C(n+m-1,m-1)
直接套用卢卡斯定理模板就可以了

代码：

#include <iostream>

#include <cstdio>

using namespace std;

#define ll long long

#define mod 1000000007

ll n,m,l,r;

ll qmul(ll a,ll b){

    ll res=;

    while(b){

        if(b&) res=(res+a)%mod;

        b>>=;

        a=(a+a)%mod;

    }

    return res;

}

ll qpow(ll a,ll b){

    ll res=;

    while(b){

        if(b&) res=qmul(res,a);

        b>>=;

        a=qmul(a,a);

    }

    return res;

}

void exgcd(ll a,ll b,ll &x,ll &y,ll &c){

    if(!b){

        x=,y=,c=a;

    }else{

        exgcd(b,a%b,y,x,c);

        y-=a/b*x;

    }

}

ll INV(ll a,ll p){

    ll x,y,c;

    exgcd(a,p,x,y,c);

    return (x%p+p)%p;

}

ll C(int a,int b){

    if(a<b) return ;

    if(b==) return ;

    if(b>a-b) b=a-b;

    ll ca=,cb=;

    for(int i=;i<b;i++){

        ca=ca*(a-i)%mod;

        cb=cb*(b-i)%mod;

    }

    return ca*qpow(cb,mod-)%mod;  //用费马小定理求逆元

    //return ca*INV(cb,mod)%mod;  //用扩展欧几里得求逆元

}

ll lucas(int a,int b){

    ll res=;

    while(a&&b){

        res=res*C(a%mod,b%mod)%mod;

        a/=mod;

        b/=mod;

    }

    return res;

}

int main(){

    scanf("%lld%lld",&m,&n);

    printf("%lld %lld\n",lucas(n-,m-),lucas(n+m-,m-));

    return ;

}

巴特西

2019西北工业大学程序设计创新实践基地春季选拔赛 D(卢卡斯定理)

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章