/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
長さ 1 の棒があります． 棒の左端から距離 x 進んだ点を，座標 x の点と呼ぶことにします．
すぬけ君はこれから N 回，以下の操作を行います．
- [0,1] の中から一様ランダムに二つの実数 x,y をとる． 座標 \min(x,y) から座標 \max(x,y) までを覆うようなシールを棒に貼る．
なお，すべての乱数は独立であるものとします．
シール同士は重なることがあります． シールが K+1 枚以上重なっている点がない時，これを良い状態と呼ぶことにします．
N 枚のシールを張り終えたあと，良い状態である確率を \text{mod }{998244353} で求めて下さい．
確率 \text{mod }{998244353} の定義
求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(N,10^5)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N K
出力
答えを出力せよ．
入力例 1
2 1
出力例 1
332748118
2 枚のシールが重ならない確率を求めればよいです．これは 1/3 になります．
入力例 2
5 3
出力例 2
66549624
入力例 3
10000 5000
出力例 3
642557092
Score : 1100 points
Problem Statement
We have a bar of length 1. A point on the bar whose distance from the left end of the bar is x is said to have a coordinate x.
Snuke will do the operation below N times.
- Choose two real numbers x and y uniformly at random from [0, 1]. Put a sticker covering the range from the coordinate \min(x,y) to the coordinate \max(x,y).
Here, all random choices are independent of each other.
Stickers can overlap. The bar is said to be good when no point is covered by K+1 or more stickers.
Find the probability, modulo 998244353, of having a good bar after putting N stickers.
Definition of a probability modulo 998244353
It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as an irreducible fraction \frac{P}{Q}, it can be proved that Q \not \equiv 0 \pmod{998244353}. Thus, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(N,10^5)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
2 1
Sample Output 1
332748118
We are to find the probability that the two stickers do not overlap, which is 1/3.
Sample Input 2
5 3
Sample Output 2
66549624
Sample Input 3
10000 5000
Sample Output 3
642557092