201375: [AtCoder]ARC137 F - Overlaps

Memory Limit：1024 MB Time Limit：6 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

有一根长度为 $1$ 的棍子。我们称棍子上与左端点的距离为 $x$ 的点的坐标为 $x$。 Sunke 会执行下述操作 $n$ 次。 - 在区间 $[0,1]$ 中均匀随机地选择两个实数 $x, y$。在棍子上贴一张从坐标为 $\min(x, y)$ 的点到坐标为 $\max(x, y)$ 的点的贴纸。 选择间互相独立。 贴纸可以互相覆盖。我们得到了一根好的棍子，当且仅当操作执行完后棍子上没有任意一点被贴纸覆盖了 $k + 1$ 次或更多次。 给定 $n, k$，请计算得到好的棍子的概率在模 $998244353$ 意义下的值。 $1\le n\le 2\times 10^5, \ 1\le k\le \min(n, 10^5)$。

Source/Category

加入题单

上一题 下一题 算法标签：