Description
我们有n个相同的弹珠，k个相同的盒子。现在随机的将每个弹珠扔进盒子中，使得最终每个盒子非空，求出一共有多少种不同的方案。两种方案不同当且仅当将盒子中的弹珠数最小表示后不同。由于方案数可能非常多，出题人又良心的不让你们写高精度，把答案摸998244353输出即可。
Input
第一行输入两个正整数n，k。
Output
输出共一行，一个整数表示Ans mod 998244353的值
Solution
以下皆为100分方法，皆可AC。
方法一：
类似第二类????????????????????????????????数的，我们将方案分成两种：
1.至少包含一个 1 的；
2.一个 1 都不包含。
设????[????][????]表示答案，那么表示1.的答案即为????[???? − 1][???? − 1]，
表示2.的答案 即为????[???? − ????][????](相当于把每个数都加上1)，
所以有： ????[????][????] = ????[???? − 1][???? − 1] + ????[???? − ????][????]，时间O(????????)。
方法二：
如图：
可找到规律,设n=0，k=1是结果为1，
则第n行第k列=第(n-k)行第一列到第k列的和。
代码
方法一：
1 const 2 mo=998244353; 3 var 4 n,k:longint; 5 f:array [0..5001,0..5001] of longint; 6 function min(o,p:longint):longint; 7 begin 8 if o<p then exit(o); 9 exit(p); 10 end; 11 12 procedure main; 13 var 14 i,j:longint; 15 begin 16 f[0,0]:=1; 17 for i:=1 to n do 18 for j:=1 to min(i,k) do 19 f[i,j]:=(f[i-1,j-1]+f[i-j,j]) mod mo; 20 end; 21 22 begin 23 readln(n,k); 24 main; 25 writeln(f[n,k]); 26 end.
方法二：
const mo=998244353; var n,k:longint; sum:array [0..5001] of longint; f:array [0..5001,0..5001] of longint; procedure main; var i,j:longint; begin for i:=0 to 5000 do begin f[i,1]:=1; sum[i]:=1; end; for i:=2 to 5000 do begin for j:=i to 5000 do f[j,i]:=(sum[j-i]+f[j-i,i]) mod mo; for j:=i to 5000 do sum[j]:=(sum[j]+f[j,i]) mod mo; end; end; begin readln(n,k); main; writeln(f[n,k]); end.