有n个无差别的物品,将它们划分成不超过m组。求出划分方法数模M的余数。
输入:
3 4 10000
输出:
4(1+1+2=1+3=2+2=4)
定义:dp[i][j] = j的i划分的总数
#include#include using namespace std;int n, m, M;int dp[1000][1000];void solve(){ dp[0][0] = 1; for (int i = 1; i <= m; i++){ for (int j = 0; j <= n; j++){ if (j - i >= 0){ dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % M; } else{ dp[i][j] = dp[i - 1][j]; } } } printf("%d\n", dp[m][n]);}int main(){ while (scanf("%d%d%d", &m, &n, &M) != EOF){ solve(); } return 0;}