Perpetual Subtraction
Contest: VK Cup 2018 - Round 1
Difficulty rating: 3100
Tags: fft, math, matrices

There is a number x initially written on a blackboard. You repeat the following action a fixed amount of times:

1. take the number x currently written on a blackboard and erase it
2. select an integer uniformly at random from the range [0, x] inclusive, and write it on the blackboard

Determine the distribution of final number given the distribution of initial number and the number of steps.

Input format:
The first line contains two integers, N (1 ≤ N ≤ 105) — the maximum number written on the blackboard — and M (0 ≤ M ≤ 1018) — the number of steps to perform.

The second line contains N + 1 integers P0, P1, ..., PN (0 ≤ Pi < 998244353), where Pi describes the probability that the starting number is i. We can express this probability as irreducible fraction P / Q, then $$P_i \equiv PQ^{-1} \pmod{998244353}$$. It is guaranteed that the sum of all Pis equals 1 (modulo 998244353).

Output format:
Output a single line of N + 1 integers, where Ri is the probability that the final number after M steps is i. It can be proven that the probability may always be expressed as an irreducible fraction P / Q. You are asked to output $$R_i \equiv PQ^{-1} \pmod{998244353}$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first case, we start with number 2. After one step, it will be 0, 1 or 2 with probability 1/3 each.

In the second case, the number will remain 2 with probability 1/9. With probability 1/9 it stays 2 in the first round and changes to 1 in the next, and with probability 1/6 changes to 1 in the first round and stays in the second. In all other cases the final integer is 0.

Example input:
2 1
0 0 1

Example output:
332748118 332748118 332748118

Example input:
2 2
0 0 1

Example output:
942786334 610038216 443664157

Editorial:
We can model this process as a Markov chain with N + 1 states with transition matrix
$$$$
The task is to find R = AM·P. A naive solution using Matrix exponentiation is obviously too slow, as it uses $${\mathcal{O}}(N^{3}\log M)$$ time. We need to improve upon it and we look for eigenvalue decomposition.
This is a triangular matrix, thus its eigenvalues are the elements on the main diagonal. Hence
$$$$
We can show that the eigenvector corresponding to $$\lambda_{i}=\frac{1}{i+1}$$ is $$v_{i} = \left( (-1)^{i+j} \cdot {i \choose j} \right)_{j=0}^{N}$$ (consult proof at the end).
Thus, we have $$Q = \begin{pmatrix} 1 & -1 & 1 & -1 & \dots & (-1)^N \\ 0 & 1 & -2 & 3 & \dots & (-1)^{N+1}\binom{N}{1} \\ 0 & 0 & 1 & -3 & \dots & (-1)^{N+1}\binom{N}{2} \\ 0 & 0 & 0 & 1 & \dots & (-1)^{N+1}\binom{N}{3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 \end{pmatrix}$$
To finalise the eigenvalue decomposition, we need to find the inverse of Q. It can be shown Q and Q - 1 are the same up to the sign (consult proof at the end): $$$$
The advantage of eigendecomposition is that AM = Q·ΛM·Q - 1,  where the diagonal matrix Λ can be exponentiated in $${\mathcal{O}}(N\log M)$$.
We can calculate the result as R = AM·P = Q·(ΛM·(Q - 1·P)) .
Performed naively, this runs in $${\mathcal {O}}(N^{2}+N\log M)$$, which is still too slow. We obviously need to multiply with Q (and its inverse) faster.
Fortunately, both linear functions Q and Q - 1 are a convolution and we can compute the multiplication in $${ \mathcal { O } } ( N \log N )$$ using FFT, which is a bit hinted by the modulus in which to compute the answer.
Proof of the eigenvectors
We show that $$\forall i \in [0,N], k \in [0,N]$$ it holds
$$$$
where the fifth equality can be proven by induction on i - k.
Proof of the inverse
Denote P = QQ - 1.
First, we show that the diagonal of the product only contains ones. This is easy, since the i-th row of Q has zeroes until i - 1-th column, i-th column of Q - 1 has zeroes starting from i + 1-th row, and Qi, i = Q - 1i, i = 1. Thus, Pi, i = 1. Next we show that the Pi, j = 0 for i ≠ j. When i > j, all the summands in the inner product are zero. It remains to show the claim for i < j.
$$P_{i,j} = \sum_{k=0}^{N} Q_{i,k} Q^{-1}_{k,j}
= \sum_{k=0}^{N} (-1)^{i+k} \binom{k}{i} \cdot \binom{j}{k}
= \sum_{k=i}^{j} (-1)^{i+k} \frac{j!}{(j-k)!(k-i)!}
= \frac{j!}{i!(j-i)!} \sum_{k=i}^{j} (-1)^{i+k} \binom{j-i}{k-i}
= \frac{j!}{i!(j-i)!} \sum_{k=0}^{j-i} (-1)^{k} \binom{j-i}{k}
= \binom{j}{i} \cdot (1-1)^{j-i} = 0$$
Proof that Q and Q - 1 are convolutions
Put y = Q - 1x. We want to show that y can be computed by convolution. See that
$$$$
hence y is a convolution of functions f and g up to some multiplicative factors.
The proof for Q is similar, we can just remove all the ( - 1)α terms.