2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛) Chino with Equation(组合公式)

时间：2021-03-12 04:49:39

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

题目描述

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

2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛) Chino with Equation(组合公式)

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

输入描述:

两个正整数m, n

输出描述:

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

9

 + 7) 即可。
示例1

输入

复制

4 7

输出

复制

20 120

思路:这道题我们可以抽象成 有n个球 要放在m个箱子里面 箱子不能为空的方案数 和箱子可以为空的方案数 这样我们就能插空法解决这道题

想像n-1个空位要插m-1个间隙 就是C（n-1，m-1） 同理  想像n+m-1个空位要插m-1个间隙 就是C（n-1，m-1） 在其中求下逆元即可

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define ll long long int

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

ll fact[];

void f(){

    fact[]=;

    for(ll i=;i<=;i++) fact[i]=fact[i-]*i%mod;

}

ll q_pow(ll a,ll n){

    ll ans=; ll base=a;

    while(n){

        if(n&) ans=(ans*base)%mod;

        base=base*base%mod;

        n>>=;

    }

        return ans;

}

ll inv(ll a,ll b){

    return q_pow(a,b-);

}

ll C(ll n,ll m){

    return fact[n]*(inv(fact[n-m]*fact[m]%mod,mod)%mod)%mod;

}

int main(){

    ios::sync_with_stdio(false);

    ll m,n;

    f();

    while(cin>>m>>n){

        cout<<C(n-,m-)<<" "<<C(m+n-,m-)<<endl;

    }

}

相关文章