题目描述

blablabla

样例

blablabla

算法1

(隔板法+组合数逆元法)

//思路：原问题为将n分成m份，其中每一份要>=0
//对这个问题直接求组合数是不好求的，可以将其转化：
//将答案的每一份均加上1，总和就变为了n+m.则问题转化为将n+m分成m份，其中每一份要>=1;
//这个问题的每一个解的每一个数都减去1，就等价于原问题的解(方案数是一样的)
//而每一份均不为空，就可以方便地利用隔板法来求解–相当于n+m个小球，往其中的n+m-1个
//空隙内添加m-1个隔板，且每两个隔板不能在一个空隙中，则答案为C[n+m-1][m-1]

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

int n,m;
const int mod=1e6+3;
int fact[700010],infact[700010];

ll qmi(int a,int b,int p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        b>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

void init()//预处理每个数的阶乘和阶乘的逆元
{
    fact[0]=infact[0]=1;
    for(int i=1;i<=700000;i++) 
    {
        fact[i]=(ll)fact[i-1]*i%mod;
        infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
}

ll C(int a,int b)
{
    return (ll)fact[a]%mod*infact[a-b]%mod*infact[b]%mod;
}


int main()
{
    cin>>n>>m;
    init();
    ll sum=0;
    for(int i=m+1;i<=m+n;i++)
    {
        sum=(sum+C(i-1,m-1))%mod;
    }
    cout<<sum;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla