[C++知识库]划分数（挑战程序设计竞赛）

有 nn 个无区别的物品, 将它们划分成不超过 m?组,求划分方法数模 MM 的余数

输入

• 输入第一行有三个整数?n、m、M
• 1 \leq m \leq n \leq 10001≤m≤n≤1000
• 1 \leq M \leq 10^41≤M≤104

输出

• 输出一个整数表示划分方法数模?MM?的余数

样例 1

输入

4 3 10000

输出

4

详细解析：

https://www.papamelon.com/post/roCHZaxsG7uh8lCWwMsuY1M364pLVJ5h

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

const int MAXSIZE = 1005;

int f[MAXSIZE][MAXSIZE];

int main() {
    int n, m, mod;

    cin >> n >> m >> mod;

    memset(f, 0, sizeof f);
    for (int j = 0; j <= m; j++) f[0][j] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++){
            f[i][j] = f[i][j - 1];
            if (i >= j) f[i][j] += f[i - j][j];
            f[i][j] %= mod;
        }
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
            cout<<f[i][j]<<" ";
        cout<<endl;
    }

    cout << f[n][m] << endl;
    return 0;
}