常数国与 Hack 国近年来战火纷飞。
常数国共有 n 个城市，每两个城市之间均有一条交通线联通。如今常数国遭到 Hack 国的重创，岌岌可危。Hack 国国王小 K 决定轰炸常数国的交通线，对常数国发起最后的攻击。
面对危难之时，常数国国王决定更换首都。在 Hack 国的轰炸结束之后，常数国的领土将会分成若干个联通块。常数国的首都，将会从联通块大小最大的联通块中，随机选择一个城市，作为首都。
小 K 得知了常数国的应对方案之后，他想知道，Hack 国有多少种不同的轰炸方案，使得常数首都所在的联通块大小恰好为 k。两种轰炸方案是不同的，当且仅当一条交通线在一种方案中存在，在另一种方案中被轰炸。由于方案数可能很大，你需要输出方案数对 998,244,353 取模的结果。
从文件bomb.in中读入数据。 共一行，两个整数 n,k ，表示常数国城市的个数与首都所在联通块大小。
输出到文件bomb.out中。 共一行，表示 Hack 国的轰炸方案数对 998,244,353 取模后的结果。
Sample Input 1 3 2
Sample Input 2 5 3
Sample 3 见选手目录下的bomb/bomb3.in与bomb/bomb3.ans。 该组样例的数据范围同第 8 个测试点。
Sample Output1 3
Explanation 3 种方案分别为，仅保留 1 号城市与 2 号城市的交通线，仅保留 2 号城市与3 号城市的交通线，仅保留 1 号城市与 3 号城市的交通线。
Sample Output2 80
对于 100% 的数据，满足 1 ≤ k ≤ n ≤ 2 × 10 3 。除此之外，对于每个数据点，还满足以下限制。
套路题，然而我还是不会 设 f [ i ] f[i] f[i] 表示大小为 i i i 的保证联通的图的个数 那么怎么求 f [ i ] f[i] f[i] 呢？正难则反！！！用总数减去不连通的情况数
设 h [ i ] h[i] h[i] 表示大小为 i i i 的不保证联通的图的个数，显然有 h [ i ] = 2 C i 2 h[i]=2^{C^2_i} h[i]=2Ci2 为了不重不漏，我们将枚举的 j j j 强制表示为编号最小的节点所在联通块的大小 那么 f [ i ] f[i] f[i] 可以写成这样 f [ i ] = h [ i ] − ∑ j = 1 i − 1 C i − 1 j − 1 ∗ f [ i ] ∗ h [ i − j ] f[i]=h[i]-\sum_{j=1}^{i-1}C_{i-1}^{j-1}*f[i]*h[i-j] f[i]=h[i]−∑j=1i−1Ci−1j−1∗f[i]∗h[i−j]
设 g [ i ] g[i] g[i] 表示大小为 i i i 的图中最大联通块大小不超过 i i i 的图的个数 于是有如下转移 g [ i ] = ∑ j = 1 m i n ( i , k ) C i − 1 j − 1 ∗ f [ j ] ∗ g [ i − j ] g[i]=\sum_{j=1}^{min(i,k)}C_{i-1}^{j-1}*f[j]*g[i-j] g[i]=∑j=1min(i,k)Ci−1j−1∗f[j]∗g[i−j]
由于 g g g 表示最大联通块大小 < = k <=k <=k 的情况 我们类似地设一个 g 1 g1 g1 表示最大联通块大小 < = k − 1 <=k-1 <=k−1 的情况 转移方程就是将上方的 k k k 换成 k − 1 k-1 k−1 就好了
最终答案就是 g [ n ] − g 1 [ n ] g[n]-g1[n] g[n]−g1[n] 时间复杂度 O ( N 2 ) O(N^2) O(N2)
