Tournament of Gold
Practice
0 (0 votes)
Strategies and expected values
Dynamic programming
Algorithms
Medium
Problem
100% Success 2 Attempts 30 Points 2s Time Limit 512MB Memory 1024 KB Max Code

Bob is organizing the annual tournament of gold. There are \(n\) participants in a line, each starting with \(0\) gold. Initially, the entire row of participants is "selected". A round of the tournament proceeds as follows:

  1. Bob selects a random subarray of the currently "selected" part of the row. Each subarray has equal probability of being chosen, including the same currently "selected" part.
  2. He gives \(1\) gold to each participant in the subarray.
  3. He sets this subarray as the new "selected" part of the row.

After \(k\) rounds of the tournament proceed, what is the expected amount of gold of each participant ?

It can be proven that the expected amount of gold for the \(i^{th}\) participant can be represented as a fraction  \(\dfrac{P_i}{Q_i}\) with \(Q_i \neq 0\) and \(gcd(P_i,Q_i)=1\). Print \(n\) space-separated integers, the \(i^{th}\) of which is \(P_i \cdot Q_i^{-1}\)  modulo $$ 998244353 $$

It can be proved that $$ Q^{-1}$$ Modulo $$ 998244353$$ exists under the following constraints. 

Input Format:

The first and only line of input contains two space-separated integers, \(n\) and \(k\).

Output Format:

Print $$ n $$ space separated integers, the $$i^{th}$$ integer denoting the answer for the $$i^{th}$$ participant .

Constraints:

\(1 \le n,k \le 500\)

Note that the Expected Output Feature for Custom Invocation is not supported for this contest. 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
58 votes
Tags:
AlgorithmsApprovedEasyGraphsOpen
Points:20
3 votes
Tags:
Easy
Points:30
16 votes
Tags:
ArraysBasic ProgrammingBasics of ImplementationEasyImplementationLogic-BasedLogical Reasoning