不定方程正整数解的个数

假设有$k + 1$个球，则有$k$个空位，在这$k$个空位中选择$n$个插入隔板，方案数就是不定方程正整数解的个数。

建立映射关系：$a_i$等于第$i$个区间的小球数量，二者一一对应

序列数量

给定整数 $n,m$。

请你计算，一共有多少个长度为 $m$ 的非负整数序列 $a_1, a_2, …, a_m$ 满足 $1\leq a_1 + a_2 + … + a_m\leq n$。

由于结果可能很大，你只需要输出对 $10^6 + 3$ 取模后的结果。

输入格式

共一行，包含两个整数 $n,m$。

输出格式

一个整数，表示满足条件的非负整数序列数量对 $10^6 + 3$ 取模后的结果。

数据范围

前 $3$ 个测试点满足 $1\leq n,m\leq 5$。
所有测试点满足 $1\leq n\leq 5 \times 10^5, 1\leq m\leq 2 \times 10^5$。

输入样例1：

1
5 1

输出样例1：

1
5

输入样例2：

1
2 2

输出样例2：

1
5

输入样例3：

1
3 2

输出样例3：

1
9

思路

这是一个不等式，添加 $a_{m+1}$ 使之变成等式 :

这样只需减去一个不合法状态，即 $a_{m+1} = n$ 即可；

进一步，为了得到之前所述不定方程的形式，建立一一对应：

,

方程转化为:

;

则问题答案为$C_{n + m}^{m} - 1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int M  = 1e6 + 3;

int n,m;

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

int C(int a,int b) {
    int res = 1;
    for(int i = 1, j = a; i <= b; ++ i, -- j) {
        res = (LL) res * j % M;
        res = (LL) res * qmi(i, M - 2) % M;
    }
    return res;
}

int main() {
    cin >> n >> m;
    cout << C(n + m,m) - 1;
    return 0;
}