题目链接： 洛谷：https://www.luogu.org/problemnew/show/P1025 JZOJ：https://jzoj.net/senior/#main/show/5195 将 n n n个弹珠分成 k k k份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
我们先来讨论一下放的方法。 为了使任意两份互不相同，那么就让第一份的珠子数量 ≥ \geq ≥第二份珠子的数量 ≥ . . . ≥ \geq...\geq ≥...≥第 k k k分珠子的数量。这样可以保证不会出现相同的方案（例如 2 , 3 , 4 2,3,4 2,3,4和 2 , 4 , 3 2,4,3 2,4,3就是相同的方案，其中至少一个会不符合要求）。 很容易想到用 f [ i ] [ j ] f[i][j] f[i][j]表示已经将 i i i个珠子分成 j j j分的方案数。为了保证 s 1 ≥ s 2 ≥ . . . ≥ s k s_1\geq s_2\geq...\geq s_k s1≥s2≥...≥sk，那么就有两种方程：
下一个格子（第 i i i个格子）放入一个珠子。由于前面的每一份都至少有一个珠子，并且保证 s 1 ≥ s 2 ≥ . . . ≥ s i − 1 s_1\geq s_2\geq...\geq s_{i-1} s1≥s2≥...≥si−1，所以在下一份放入一个珠子也是可以保证 s 1 ≥ s 2 ≥ . . . ≥ s i s_1\geq s_2\geq...\geq s_{i} s1≥s2≥...≥si的。所以就有 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i−1][j−1]前面的每一个格子都多放一个珠子。由于本来就有 s 1 ≥ s 2 ≥ . . . ≥ s i s_1\geq s_2\geq...\geq s_{i} s1≥s2≥...≥si，那么也就必然有 s 1 + 1 ≥ s 2 + 1 ≥ . . . ≥ s i − 1 + 1 ≥ s i s_1+1\geq s_2+1\geq...\geq s_{i-1}+1\geq s_i s1+1≥s2+1≥...≥si−1+1≥si。那么方程就是 f [ i ] [ j ] = f [ i − j ] [ j ] f[i][j]=f[i-j][j] f[i][j]=f[i−j][j]所以综合起来就是 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i − j ] [ j ] f[i][j]=f[i-1][j-1]+f[i-j][j] f[i][j]=f[i−1][j−1]+f[i−j][j]
洛谷：
#include <cstdio> #include <iostream> using namespace std; int f[201][201],n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) f[i][1]=1; for (int i=2;i<=n;i++) for (int j=2;j<=i;j++) f[i][j]=f[i-1][j-1]+f[i-j][j]; printf("%d\n",f[n][m]); return 0; }JZOJ:
#include <cstdio> #define N 5100 #define MOD 998244353 using namespace std; int f[N][N],n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) f[i][1]=1; for (int i=2;i<=n;i++) for (int j=2;j<=i;j++) f[i][j]=(f[i-1][j-1]+f[i-j][j])%MOD; printf("%d\n",f[n][m]); return 0; }