题目描述

直接看成小球问题
n个小球分到m个不同的盒子，允许空盒

样例

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=2*N,mod=1e6+3;
#define int long long
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;

int n,m,k;

int a[N],b[N];
int fact[N],infact[N];

int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(LL) res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
void init(){
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }
}
int C(int a,int b){
    if(b<0||b>a) return 0;
    return ((LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}
void solve(){
   cin>>n>>m;
   int res=0;
   for(int i=1;i<=n;i++){
       //i个球分成m段
       res+=C(i+m-1,m-1);
       res%=mod;
   }
   cout<<res;
}
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    init();

    //>>t;
    while(t--) solve();
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla