G. 淘汰赛 · AC 题库

第 473 场 AtCoder Beginner Contest

淘汰赛

Wipeout

AtCoder

⌀ 1974

原题

← D→

淘汰赛AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There are $N$ cards arranged face down in a row, each with one of the integers $1,2,\dots,N$ written on its face. The order of these cards is determined uniformly at random from the $N!$ possible orders. You know that there is exactly one card with each of the integers $1,2,\dots,N$ written on its face and that the cards were arranged uniformly at random, but you have no other information about the integers written on the faces of the cards.

You play the following game.

Initially, let the variable $x=1$ .
As long as $x \le N$ , repeat the following operation. One operation consists of the following three steps.
Specify one card and turn it face up.
- If the integer written on the card is $x$ , eat that card and add $1$ to $x$ .
- Otherwise, turn that card face down. You can permanently remember the integer written on that card.

You always act so that the expected value of the total number of operations until all cards have been eaten is minimized. In this case, what is the probability that the total number of operations is $K$ ? Find it modulo $998244353$ .

Definition of probability modulo $998244353$ It can be proved that the sought probability is always a rational number. Also, under the constraints of this problem, it can be proved that when the rational number to be found is expressed as an irreducible fraction $\frac{P}{Q}$ , we have $Q {{}\not\equiv{}} 0 \pmod{998244353}$ . Therefore, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353$ . Output this $R$ .

有 $N$ 张卡片正面朝下排成一列，每张卡片的正面写有 $1,2,\dots,N$ 中的一个整数。这些卡片的排列顺序从 $N!$ 种可能的顺序中等概率随机确定。你知道每个整数 $1,2,\dots,N$ 恰好分别写在一张卡片上，并且卡片是等概率随机排列的，但除此之外，你不知道卡片正面写的整数的任何信息。

你进行如下游戏。

初始时，令变量 $x=1$ 。
当 $x \le N$ 时，重复进行以下操作。一次操作由以下三个步骤组成。
指定一张卡片并将其翻开。
- 如果卡片上写的整数是 $x$ ，则吃掉这张卡片，并令 $x$ 增加 $1$ 。
- 否则，将这张卡片重新扣下。你可以永久记住这张卡片上写的整数。

你始终采取使吃掉所有卡片所需的操作总数的期望值最小的行动。在这种情况下，操作总数为 $K$ 的概率是多少？请将答案对 $998244353$ 取模后输出。

概率对 $998244353$ 取模的定义

可以证明，所求概率总是有理数。此外，在本题约束条件下，可以证明：将待求有理数表示为既约分数 $\frac{P}{Q}$ 时，有 $Q {{}\not\equiv{}} 0 \pmod{998244353}$ 。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R \lt 998244353$ 。输出这个 $R$ 。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

All input values are integers.
$1 \le N \le 5 \times 10^5$
$N \le K \le 10^9$

所有输入值均为整数。
$1 \le N \le 5 \times 10^5$
$N \le K \le 10^9$

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N K

N K

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1

3 4

Output #1

499122177

For this input, $N=3$. Let us call the cards $a,b,c$ in the order they are arranged. Below is an example of your actions when acting so that the expected value of the total number of operations is minimized. - First, turn $a$ face up. - If $1$ is written on $a$, eat that card. - Next, turn $b$ face up. - If $2$ is written on $b$, eat that card. - Next, turn $c$ face up; since $3$ is necessarily written on it, eat it. In this case, you eat all cards in three operations, and the probability of this happening is $1/6$. - If $3$ is written on $b$, turn that card face down. - Next, turn $c$ face up; since $2$ is necessarily written on it, eat it. After that, turn $b$ face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$. - If $2$ is written on $a$, turn that card face down. - Next, turn $b$ face up. - If $1$ is written on $b$, eat that card. - Next, turn $a$ face up and eat it. Next, turn $c$ face up; since $3$ is necessarily written on it, eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$. - If $3$ is written on $b$, turn that card face down. - At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is $1/6$. - If $3$ is written on $a$, turn that card face down. - Next, turn $b$ face up. - If $1$ is written on $b$, eat that card. - Next, turn $c$ face up; since $2$ is necessarily written on it, eat it. After that, turn $a$ face up and eat it. In this case, you eat all cards in four operations, and the probability of this happening is $1/6$. - If $2$ is written on $b$, turn that card face down. - At this point, it has become clear which integer is written on every one of the cards. So, perform three operations and eat all the cards in order of their numbers. In this case, you eat all cards in five operations, and the probability of this happening is $1/6$. Combining everything, the probability that the total number of operations is $3$ is $1/6$, the probability that it is $4$ is $1/2$, and the probability that it is $5$ is $1/3$. For this sample, output $499122177$, which represents $1/2$ modulo $998244353$.

Input #2

3 6

Output #2

Input #3

500000 777777

Output #3

251612105

题目信息

题号

abc473_g

所属比赛

第 473 场 AtCoder Beginner Contest

时间限制

3 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。