/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1300 点
問題文
1 から N までの番号が振られた N 人の人と、1 から K までの番号が振られた K 個の商品があります。 これから、ターン制のゲームが行われます。 ターンは、番号 1 の人、番号 2 の人、番号 3 の人、\ldots、番号 N の人、番号 1 の人 、\ldots、番号 N の人、番号 1 の人、\ldots、の順に回り、全ての商品が誰かに獲得されるまで続きます。
各ターンには、以下が行われます。
- 自分のターンが来た人がすでに商品を獲得済みの場合、何も行われない。
- そうでない場合、その人は、まだ自分が選んでいない商品から 1 つを等確率でランダムに選び、審判であるすぬけ君に秘密裏に伝える。 その商品がすでに他の誰かに獲得されていたなら、何も起こらない。そうでないなら、その商品はその人が獲得する。
各 i について、番号 i の人がいずれかの商品を獲得する確率を \bmod 998,244,353 で計算してください (注記参照)。
注記
- 商品をランダムに選ぶ行為は全て独立に行われます。
- ゲームが有限のターン数で終了することは証明可能です。
- 参加者が商品を選ぶ場面で、まだその人が選んでいない商品が必ず 1 つ以上存在することも証明可能です。
- 求めるべき確率が有理数であることも証明可能です。確率を出力する際は、まずその確率を分数 \frac{y}{x} として表してください。ここで、x, y は整数であり、x は P = 998,244,353 で割り切れてはなりません (この問題の制約の下で、そのような表現は必ず可能です)。そして、xz \equiv y \pmod{P} なる 0 以上 P - 1 以下の唯一の整数 z を出力してください。
制約
- 1 \leq K \leq N \leq 40
- 入力中の全ての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
N K
出力
N 行出力せよ。 i 行目には、番号 i の人がいずれかの商品を獲得する確率を \bmod 998,244,353 で出力すること。
入力例 1
3 2
出力例 1
1 249561089 748683265
- まず、番号 1 の人が商品を 1 個選んで獲得します。ここで商品 p が選ばれたとします。
- そして、1/2 の確率で、番号 2 の人がもう一方の商品を選んで獲得し、ゲームが終了します。
- 1/2 の確率で、番号 2 の人も商品 p を選んでしまって獲得できず、番号 3 の人のターンとなります。
- 1/4 の確率で、番号 3 の人がもう一方の商品を選んで獲得し、ゲームが終了します。
- 1/4 の確率で、番号 3 の人も商品 p を選んでしまいます。その次は番号 1 の人のターンですが、商品を獲得済みのため何もしません。その次は番号 2 の人のターンであり、商品 p は前回選んだため今回は必ずもう一方の商品を選んで獲得し、ゲームが終了します。
以上より、番号 1, 2, 3 の人がいずれかの商品を獲得する確率はそれぞれ 1, \frac{3}{4}, \frac{1}{4} です。
入力例 2
4 3
出力例 2
1 314262112 767169272 915057324
商品獲得確率はそれぞれ 1, \frac{47}{54}, \frac{77}{108}, \frac{5}{12} です。
入力例 3
40 10
出力例 3
1 868517173 27621563 837064957 222682471 512462123 662169358 927654899 421237429 47896491 462367772 888812171 300869511 63754652 144548024 358216674 895724239 274552277 722622637 946769993 579325471 777654313 142897955 607284898 8038340 863909530 63295741 862961672 335905745 944425523 358698956 299986928 847582651 197657467 180361665 412489246 762713624 410322243 646538576 79047758
Score : 1300 points
Problem Statement
There are N people numbered 1 through N, and K items numbered 1 through K. They play a turn-based game. Person 1 takes the first turn, Person 2 takes the next turn, then Person 3, \ldots, Person N, then Person 1 again, \ldots, Person N, Person 1 again, \ldots, and so on, until all items are taken.
In each turn, the following happens:
- If the person already wins an item, nothing happens.
- Otherwise, he chooses one of the items he hasn't chosen yet uniformly at random, and secretly tells it to Snuke, the judge of the game. If the item is already taken by someone else, nothing happens; otherwise he wins the item.
For each i, compute the probability that Person i wins an item, modulo 998,244,353 (as described in the Notes section).
Notes
- All random choices are made independently.
- We can prove that the game always ends in finite number of steps.
- We can also prove that, whenever a player is asked to choose an item, he has at least one item he hasn't chosen yet.
- We can also prove that the probabilities are rational numbers. When you print a probability, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by P = 998,244,353 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and P - 1, inclusive, that satisfies xz \equiv y \pmod{P}.
Constraints
- 1 \leq K \leq N \leq 40
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print N lines. On the i-th line, print the probability that the i-th person wins an item, modulo 998,244,353.
Sample Input 1
3 2
Sample Output 1
1 249561089 748683265
- First, Person 1 chooses an item (call it Item p), and wins it.
- Then, with 1/2 probability, Person 2 chooses the other item in the next turn and wins it, and the game ends.
- With 1/2 probability, Person 2 chooses p, he doesn't win it, and Person 3 takes the next turn.
- With 1/4 probability, Person 3 chooses the other item, wins it, and the game ends.
- With 1/4 probability, Person 3 chooses p again. Then, next turn is Person 1's and nothing happens because he has already won an item. Then, in the next turn, Person 2 chooses the other item for sure because he has already chosen p in his previous turn, so he wins an item this time, and the game ends.
To summarize, Person 1, 2, 3 will get an item with probability 1, \frac{3}{4}, \frac{1}{4}, respectively.
Sample Input 2
4 3
Sample Output 2
1 314262112 767169272 915057324
The probabilities are 1, \frac{47}{54}, \frac{77}{108}, \frac{5}{12}.
Sample Input 3
40 10
Sample Output 3
1 868517173 27621563 837064957 222682471 512462123 662169358 927654899 421237429 47896491 462367772 888812171 300869511 63754652 144548024 358216674 895724239 274552277 722622637 946769993 579325471 777654313 142897955 607284898 8038340 863909530 63295741 862961672 335905745 944425523 358698956 299986928 847582651 197657467 180361665 412489246 762713624 410322243 646538576 79047758