Chino with Equation 不定方程-蒲公英云

Chino with Equation 不定方程

假设未知数m个

不定方程，用插板法来想，

求正整数解：m个桶，放n件东西，每个桶至少一件： C(n-1, m-1)

求非负数解：C(n+m-1, m-1)

看m和的数据范围，用什么方式求组合数

可以用费马小定理

// Problem: Chino with Equation
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/553/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%d\n",a)
#define mem(x,y) memset(x,y,sizeof(x))
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int N=2e6+100;
ll n, m;
ll fac[N];
vector<int> v(N);
ll qmi(ll a, ll b)
{ 
    ll res = 1;
    while(b)
    { 
        if(b&1) res = res * a % mod;
        a = a * a % mod;
        b>>=1;
    }
    return res;
}
void init()
{ 
    fac[0] = 1;
    for(ll i = 1; i < N; i ++ ) fac[i] = fac[i-1] * i % mod;
}
ll cal(ll n, ll m)
{ 
    if(n < 0 or m < 0 or n < m) return 0;
    ll ans = fac[n];
    ans = ans * qmi(fac[m], mod-2) % mod;
    ans = ans * qmi(fac[n-m] ,mod-2) % mod;
    return ans;
}
void solve()
{ 
    init();
    cin >> m >> n;
    cout << cal(n-1, m-1) << " " << cal(n+m-1, m-1) << endl;
}
int main()
{ 
    ios::sync_with_stdio(false);cin.tie(0);
    solve();
    return 0;
}