409578: GYM103637 F Function analysis

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Function analysistime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Let $$$p$$$ be a sequence of numbers $$$(1, 2, 3, \dots, n-1, n)$$$, and $$$q$$$ be a random sample of $$$m \le n$$$ elements of $$$p$$$, such that $$$i$$$-th element of $$$q$$$ is chosen equiprobable and independently.

Denote by $$$nth(a, b)$$$ the element that is in the $$$b$$$-th position if we order $$$a$$$ in non-decreasing order. For example, $$$nth(a=(5,2,3,2), b=4)=5$$$.

For each $$$m$$$, s.t. $$$d \le m \le n$$$ find the probability that $$$nth(p, k) < nth(q, d)$$$, modulo $$$998244353$$$. In other words, if the desired probability is $$$\frac{P}{Q}$$$, print $$$P \cdot Q^{-1} \mod 998244353$$$.

Input

A single line of input contains three integers separated by space $$$n$$$, $$$d$$$ and $$$k$$$.

$$$$$$1 \le k \le n \le 3 \cdot 10^5$$$$$$ $$$$$$1 \le d \le n$$$$$$

Output

Print $$$n-d+1$$$ lines, each of them containing a single integer, the probability for $$$m$$$ from $$$d$$$ to $$$n$$$ both including (modulo $$$998244353$$$).

ExampleInput
5 2 3
Output
119789323
15971910
552628074
239898083

加入题单

上一题 下一题 算法标签: