第 230 场 AtCoder Regular Contest++
E
Minister
AtCoder
⌀ 3827
原题
← D→

MinisterAI (CI翻译)

Problem Statement

You are given positive integers $N$ and $M$.

A box contains one ball numbered $1$, one ball numbered $2$, $\dots$, one ball numbered $N$. There is also a blackboard with nothing written on it. Using these, Alice plays the following game.

First, Alice draws one ball from the box uniformly at random and keeps it at hand. Then, Alice performs the following sequence of operations $N-1$ times.

  • Draw one ball from the box uniformly at random, independently of the previous operations, and keep it at hand.
  • Write the sum of the numbers of the two balls at hand on the blackboard.
  • Freely choose exactly one of the two balls at hand to discard, and keep the other at hand.

Alice's score in this game is defined as follows: it is $0$ if the maximum value of the integers written on the blackboard is $M$ or greater, and otherwise it is the number of the ball finally kept at hand.

Find the expected value, modulo $998244353$, of Alice's score when she acts to maximize the expected value of her score.

Definition of expected value modulo $998244353$ It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when that value is represented as an irreducible fraction $\frac{A}{B}$, we have $B {{}\not\equiv{}} 0 \pmod{998244353}$. Therefore, there is a unique integer $C$ such that $C \times B \equiv A \pmod{998244353}, 0 \leq C < 998244353$. Report this $C$.

Constraints

  • $2 \le N \le 3000$
  • $1 \le M \le 2N$
  • All input values are integers.

Input

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

N M

Output

Output the answer.

{"titleZh":"部长","bodyZh":"## 题目描述\n\n给定正整数 $N$ 和 $M$。\n\n一个盒子中有编号为 $1$、编号为 $2$、$\dots$、编号为 $N$ 的球各一个。此外,还有一块一开始什么都没有写的黑板。Alice 使用这些物品进行如下游戏。\n\n首先,Alice 从盒子中等概率随机抽取一个球并拿在手中。然后,Alice 重复以下操作 $N-1$ 次。\n\n- 从盒子中等概率随机抽取一个球,且每次抽取都相互独立,并将其拿在手中。\n- 将手中两个球的编号之和写在黑板上。\n- 从手中的两个球中恰好选择一个丢弃,并将另一个球留在手中。\n\n该游戏中 Alice 的得分定义如下:如果黑板上写出的整数的最大值大于等于 $M$,则得分为 $0$;否则,得分为最终留在手中的球的编号。\n\n求 Alice 以最大化得分期望值的方式行动时,其得分的期望值对 $998244353$ 取模后的结果。\n\n### 期望值的模 $998244353$ 定义\n\n可以证明,所求的期望值始终为有理数。此外,在本题的约束条件下,可以证明当该值表示为最简分数 $\frac{A}{B}$ 时,有 $B {{}\\not\\equiv{}} 0 \\pmod{998244353}$。因此,存在唯一的整数 $C$ 满足 $C \\times B \\equiv A \\pmod{998244353}$ 且 $0 \\leq C < 998244353$。请输出这个 $C$。\n\n## 约束条件\n\n- $2 \\leq N \\leq 3000$\n- $1 \\leq M \\leq 2N$\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入给出,格式如下:\n\n\nN M\n\n\n## 输出格式\n\n输出答案。"}AI (CI翻译)

样例

Input #1
3 5
Output #1
665496237
The following is one possible scenario of the game. 1. One ball is drawn from the box, and its number is $3$. This ball is kept at hand. 2. One ball is drawn from the box, and its number is $1$. This ball is kept at hand. The numbers of the two balls at hand are now $1,3$. 3. Write $1+3=4$ on the blackboard. 4. Discard the ball numbered $3$, keeping the ball numbered $1$ at hand. 5. One ball is drawn from the box, and its number is $2$. This ball is kept at hand. The numbers of the two balls at hand are now $1,2$. 6. Write $1+2=3$ on the blackboard. 7. Discard the ball numbered $1$, keeping the ball numbered $2$ at hand. 8. Since the maximum value of the integers written on the blackboard is not $5$ or greater, Alice obtains a score of $2$, the number of the ball finally kept at hand. This scenario is not necessarily the result of Alice acting to maximize the expected value of her score. The sought expected value is $\dfrac{5}{3} \bmod{998244353}=665496237$.
Input #2
10 10
Output #2
0
Input #3
30 40
Output #3
377125280
题目信息
题号
arc230_e
时间限制
2 s
内存限制
1024 MB

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