201465: [AtCoder]ARC146 F - Simple Solitaire

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

Description

Score : $1200$ points

Problem Statement

The following process is carried out on a permutation $P$ of $(1,2,\dots,N)$.

We have $N$ cards, numbered $1$ to $N$. Card $i$ has the integer $P_i$ written on it.

There are an integer $X=1$ and a boy called PCT, who initially has nothing. PCT does the following procedure for each $i=1,2,\dots,N$ in this order.

  • Get Card $i$. Then, repeat the following action as long as he has a card with $X$ written on it:
    • eat the card with $X$ written on it, and then add $1$ to $X$.
  • If PCT currently has $M$ or more cards, throw away all cards he has and terminate the process, without performing any more procedures.

Here, let us define the score of the permutation $P$ as follows:

  • if the process is terminated by throwing away cards, the score of $P$ is $0$;
  • if the process is carried out through the end without throwing away cards, the score of $P$ is $\prod_{i=1}^{N-1}$ $($ the number of cards PCT has at the end of the $i$-th procedure $)$.

There are $N!$ permutations $P$ of $(1,2,\dots,N)$. Find the sum of the scores of all those permutations, modulo $998244353$.

Constraints

  • $2 \le N \le 2 \times 10^5$
  • $2 \le M \le N$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

Output

Print the answer.

Sample Input 1

3 2

Sample Output 1

1

For $P=(3,1,2)$, the process goes as follows.

  • The first procedure:
    • PCT gets Card $1$.
    • PCT currently has $1$ card, so he goes on.
  • The second procedure:
    • PCT gets Card $2$.
    • PCT eats Card $2$ and make $X = 2$.
    • PCT currently has $1$ card, so he goes on.
  • The third procedure:
    • PCT gets Card $3$.
    • PCT eats Cards $1,3$ and make $X = 4$.
    • PCT currently has $0$ cards, so he goes on.

The process is carried out through the end, so the score of $(3,1,2)$ is $1 \times 1 = 1$.

Other than $(3,1,2)$, there is no permutation with a score of $1$ or greater, so the answer is $1$.

Sample Input 2

3 3

Sample Output 2

5

Sample Input 3

146146 146

Sample Output 3

103537573

Input

题意翻译

#### 题目描述 有一个长为 $N$ 的排列 $P$ 。 在接下来的 $N$ 天里，为了救她的朋友， $\mathsf{linyue}$ 会参加一个仪式，在第 $i$ 天的行动如下所示： > 首先，$\mathsf{linyue}$ 会参加这一天的祭祀，然后获得编号为 $P_i$ 的诅咒。 > > 然后，$\mathsf{linyue}$ 会净化自己身上的诅咒。只要所有编号小于某个诅咒的诅咒都被 $\mathsf{linyue}$ 获得过，那么这个诅咒就会被净化。（特别地，$1$ 号诅咒总是能被净化） > > 最后，如果此时 $\mathsf{linyue}$ 身上有不少于 $M$ 种不同的诅咒，那么这个仪式会立刻结束。 这个仪式的贡献是前 $N-1$ 天里每一天结束时 $\mathsf{linyue}$ 身上未净化的诅咒的数量之积。当然，如果仪式中止，贡献就是 $0$。 理论上在第 $N$ 天，$\mathsf{linyue}$ 会获得并净化所有 $N$ 种诅咒，她的朋友也能恢复健康，这样一切都能恢复如初！当然，这需要仪式能有足够的贡献。仪式的贡献只和排列 $P$ 有关，所以 $\mathsf{linyue}$ 希望你能对于所有 $N!$ 种排列 $P$，求仪式的贡献和。 #### 数据范围 $2 ≤ N ≤ 2 × 10^5$ $2 ≤ M ≤ N$ #### 样例解释 对于第 $1$ 组样例，$N=3,M=2$。唯一一个可以让仪式有贡献的 $P$ 是 $(3,1,2)$。此时，$\mathsf{linyue}$ 会在第一天获得 $3$ 号诅咒，在第二天获得并净化 $1$ 号诅咒，因此有 $1$ 的贡献。对于其他的排列，如果 $P_3=1$，那么就会导致她在第二天结束时有 $2$ 种诅咒而中止仪式，否则就会导致在前两天里有一天结束时身上未净化诅咒数量为 $0$ 而使得乘积为 $0$。 translated by 隔壁泞2的如心

Source/Category

加入题单

上一题 下一题 算法标签：