/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1200 点
問題文
正整数 N,M が与えられます.
箱の中に 1,2,\dots, N の番号がついたボールがそれぞれ 1 つずつ入っています. また，何も書き込まれていない黒板があります. Alice はこれらを使って次のようなゲームを行います.
まず Alice は箱の中から一様ランダムに 1 つのボールを取り出し，手元に置きます. その後，Alice は次の一連の操作を N-1 回行います.
- 箱の中からそれまでの操作と独立に一様ランダムに 1 つのボールを取り出し，手元に置く.
- 手元にある 2 つのボールの番号の和を黒板に書き込む.
- 手元にある 2 つのボールのうちちょうど一方を自由に選んで捨て，もう一方を手元に残す.
このゲームで Alice が得るスコアは，黒板に書き込まれた整数の最大値が M 以上である場合は 0 で，そうでない場合は最終的に手元に置かれているボールの番号であると定めます.
Alice が自身の得られるスコアの期待値が最大となるように行動するときの，Alice が得るスコアの期待値を \text{mod }{998244353} で求めてください.
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{A}{B} で表した時、B {{}\not\equiv{}} 0 \pmod{998244353} となることも証明できます。 よって、C \times B \equiv A \pmod{998244353}, 0 \leq C < 998244353 を満たす整数 C が一意に定まります。 この C を答えてください。
制約
- 2 \le N \le 3000
- 1 \le M \le 2N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる.
N M
出力
答えを出力せよ.
入力例 1
3 5
出力例 1
665496237
ゲームのシナリオとしては次のようなものが考えられます.
- 1 つのボールを箱から取り出したところ，その番号は 3 であった. そのボールを手元に置く.
- 1 つのボールを箱から取り出したところ，その番号は 1 であった. そのボールを手元に置く. 手元にある 2 つのボールの番号は 1,3 となる.
- 黒板に 1+3=4 を書き込む.
- 3 の番号がついたボールを捨て，1 の番号がついたボールが手元に残る.
- 1 つのボールを箱から取り出したところ，その番号は 2 であった. そのボールを手元に置く. 手元にある 2 つのボールの番号は 1,2 となる.
- 黒板に 1+2=3 を書き込む.
- 1 の番号がついたボールを捨て，2 の番号がついたボールが手元に残る.
- 黒板に書き込まれた整数の最大値は 5 以上ではないため，Alice は最終的に手元に置かれているボールの番号である 2 のスコアを得る.
このシナリオは，Alice が自身の得られるスコアの期待値が最大となるように行動した結果であるとは限りません.
求める期待値は \dfrac{5}{3} \bmod{998244353}=665496237 です.
入力例 2
10 10
出力例 2
0
入力例 3
30 40
出力例 3
377125280
Score : 1200 points
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.
Sample Input 1
3 5
Sample Output 1
665496237
The following is one possible scenario of the game.
-
One ball is drawn from the box, and its number is 3. This ball is kept at hand.
-
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.
-
Write 1+3=4 on the blackboard.
-
Discard the ball numbered 3, keeping the ball numbered 1 at hand.
-
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.
-
Write 1+2=3 on the blackboard.
-
Discard the ball numbered 1, keeping the ball numbered 2 at hand.
-
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.
Sample Input 2
10 10
Sample Output 2
0
Sample Input 3
30 40
Sample Output 3
377125280