题目说人话

• 给定一个n和m
• 求满足1 <= a1 + a2 + ... + am <= n的总共方案数
• 要求任意ai >= 0
• 结果对1e6+3取余数

输入

• 输入两个数n和m

5 1

输出

• 一个整数，表示总共方案数取模后的结果

5

算法 (数论，组合数，逆元) $O(n + m)$

• 题目要求求$1<=a_1+a_2+…+a_m<=n$的总方案数
• 我们可以先求$a_1+a_2+…+a_m+a_{m+1}=n$的总方案数量，将不等式转换为等式，这个式子中每一项都满足$a_i>=0$
• 如果我们对每一个$a_i$都加上1，则总共满足条件的方案数不变，转换为求$b_1+b_2+…+b_m+b_{m+1}=n+m+1$的方案总数，其中$b_i>=1$，这个方案数可以使用隔板法求得，结论为$c^m_{n+m}$
• 这和原题目要求求的问题有什么关系呢？我们只需要在上面求得的方案数减1就行了，因为上面求得的方案数中，只是多包含了$0+0+…+0+n=n$这一种方案，因为此时只有$a_{m+1}=n$，其余都为0，而题目要求$a_i>=0$
• 看数据范围过1e5了，使用板子组合数二的板子就行。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;

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

int c(int a, int b, int p){
    LL ta = 1, tb = 1, tab = 1;
    for(int i=1; i<=a; i++){
        ta = ta * i % p;
        if(i <= b)
            tb = tb * i % p;
        if(i <= a - b)
            tab = tab * i % p;
    }
    int ans = (LL)ta * qmi(tb, p - 2, p) % p;
    ans = (LL)ans * qmi(tab, p - 2, p) % p;
    return ans;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int p = 1e6 + 3;
    int ans = c(n + m, m, p);
    cout << ans - 1<< endl;
    return 0;
}