UOJ Logo Universal Online Judge

UOJ

#449. 【集训队作业2018】喂鸽子

统计

小Z是养鸽子的人。一天,小Z给鸽子们喂玉米吃。一共有n只鸽子,小Z每秒会等概率选择一只鸽子并给他一粒玉米。一只鸽子饱了当且仅当它吃了的玉米粒数量$\ge k$。 小Z想要你告诉他,期望多少秒之后所有的鸽子都饱了。

假设答案的最简分数形式为$\frac{a}{b}$,你需要求出$w$,满足$a \equiv b \cdot w \pmod{998244353} \; (0 \le w < 998244353)$。

ps:为了方便选手确认自己程序的正确性,下发文件中包含一个模拟器的源码,请选手自行编译。该模拟器会无限地重复模拟题目中描述的过程,并将每次模拟的秒数的平均值以实数的形式输出,该模拟器能够保证$3 \sim 4$位有效数字的精确度。

输入格式

一行两个正整数$n,k$。

输出格式

一行一个数表示答案。

样例一

input

1 1

output

1

限制与约定

本题采用子任务的方式评测。

子任务一($4pts$):$n = 1$。

子任务二($11pts$):$k = 1$。

子任务三($19pts$):$k = 2$。

子任务四($46pts$):$k \le 50$。

子任务五($20pts$):无特殊限制。

对于所有的数据,$n \le 50$,$k \le 1000$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{256MB}$

下载

样例数据及模拟器下载