Koishi's Unconscious Permutation
Contest: Codeforces Round 796 (Div. 1)
Difficulty rating: 3500
Tags: fft, math

Koishi is unconsciously permuting $$$n$$$ numbers: $$$1, 2, \ldots, n$$$.

She thinks the permutation $$$p$$$ is beautiful if $$$s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$$$. $$$[x]$$$ equals to $$$1$$$ if $$$x$$$ holds, or $$$0$$$ otherwise.

For each $$$k\in[0,n-1]$$$, she wants to know the number of beautiful permutations of length $$$n$$$ satisfying $$$k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

Input format:
There is one line containing two intergers $$$n$$$ ($$$1 \leq n \leq 250\,000$$$) and $$$s$$$ ($$$0 \leq s < n$$$).

Output format:
Print one line with $$$n$$$ intergers. The $$$i$$$-th integers represents the answer of $$$k=i-1$$$, modulo $$$998244353$$$.

Constraints:
Time limit: 12.0 s
Memory limit: 1024.0 MB

Note:
Let $$$f(p)=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

Testcase 1:

$$$[2,1]$$$ is the only beautiful permutation. And $$$f([2,1])=0$$$.

Testcase 2:

Beautiful permutations:

$$$[1,2,4,3]$$$, $$$[1,3,4,2]$$$, $$$[1,4,2,3]$$$, $$$[2,1,3,4]$$$, $$$[2,3,1,4]$$$, $$$[3,1,2,4]$$$, $$$[3,4,2,1]$$$, $$$[4,2,3,1]$$$, $$$[4,3,1,2]$$$. The first six of them satisfy $$$f(p)=2$$$, while others satisfy $$$f(p)=1$$$.

Example input:
2 0

Example output:
1 0

Example input:
4 1

Example output:
0 3 6 0

Editorial:
We call a permutation $$$p$$$ of length $$$n-s$$$ is **good** if $$$\forall i\in[1,n-s-1],p_i+1\not=p_{i+1}$$$.
If we can calculate $$$$$$ Ans_k=\sum\limits_{p\ is\ \text{good}}[\sum\limits_{i=1}^{n-s-1}[p_i<p_{i+1}]=k] $$$$$$ then, we can get the answer easily by *Binomial inversion*. So we just need to focus on how to calculate $$$Ans_k$$$. Conveniently, let $$$n\rightarrow n-s$$$. We have: $$$$$$ ans_k = \sum_{i=0}^{k} \binom{n-1}{i} (-1)^i \left\langle\begin{matrix} n-i\\n-k-1 \end{matrix}\right\rangle $$$$$$ Where $$$\left\langle\begin{matrix} n\\m \end{matrix}\right\rangle$$$ is the Eulerian number. As we know, the generate function of Eulerian number is: $$$$$$ \left\langle\begin{matrix} n\\m \end{matrix}\right\rangle = [x^my^n]\dfrac{n!(x-1)}{x-e^{(x-1)y}} $$$$$$ So we have: $$$$$$ ans_k = \sum_{j=0}^{k} \binom{n-1}{j} (-1)^j \left\langle\begin{matrix} n-j\\n-k-1 \end{matrix}\right\rangle\\ = [x^{n-k-1}] \sum_{j=0}^{k} \binom{n-1}{j} (-1)^j [y^{n-j}]\dfrac{(n-j)!(x-1)}{x-e^{(x-1)y}}\\ = [x^{n-k-1}] \sum_{j=0}^{k} \dfrac{(n-1)!}{j!} (-1)^j (n-j)[y^{n-j}]\dfrac{x-1}{x-e^{(x-1)y}}\\ = [x^{n-k-1}] \sum_{j=0}^{k} \dfrac{(n-1)!}{j!} (-1)^j [y^{n-j-1}]\dfrac{\text{d}}{\text{d}y}\dfrac{x-1}{x-e^{(x-1)y}}\\ =(n-1)![x^{n-k-1}] \sum_{j=0}^{k} \dfrac{(-1)^j}{j!} [y^{n-j-1}] \dfrac{(x-1)^2e^{(x-1)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] \sum_{j=0}^{k} [y^j]e^{-y} [y^{n-j-1}] \dfrac{(x-1)^2e^{(x-1)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] \sum_{j=0}^{k} [y^{n-1}] \dfrac{(x-1)^2e^{(x-2)y}}{(x-e^{(x-1)y})^2}\\ =(n-1)![x^{n-k-1}] \sum_{j=0}^{k} [y^{n-1}] \dfrac{(x-1)^2e^{xy}}{(xe^y-e^{xy})^2}\\ =(n-1)![x^{n-k-1}] \sum_{j=0}^{k} [y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2}\\ $$$$$$
Let's consider how to calculate $$$[y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2}$$$. Let $$$u=(1-x)y$$$ and we have: $$$$$$ [y^{n-1}] \dfrac{(x-1)^2e^{-xy}}{(xe^{(1-x)y}-1)^2} = (1-x)^{n+1} [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(xe^u-1)^2}\\ = (1-x)^{n+1} [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(1-xe^u)^2} $$$$$$ And: $$$$$$ [u^{n-1}] \dfrac{e^{\frac{-xu}{1-x}}}{(1-xe^u)^2}\\= [u^{n-1}] \sum_{i=0} (i+1)x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n-1}]\sum_{i=0}(i+\frac{1}{1-x}+\frac{-x}{1-x})x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n-1}] \sum_{i=0}(i-\frac{x}{1-x})x^ie^{(i-\frac{x}{1-x})u}+ [u^{n-1}]  \frac{1}{1-x}\sum_{i=0}x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n}] \sum_{i=0}nx^ie^{(i-\frac{x}{1-x})u}+ [u^{n-1}] \frac{1}{1-x}\sum_{i=0}x^ie^{(i-\frac{x}{1-x})u}\\= [u^{n}] \dfrac{ne^{-\frac{xu}{1-x}}}{1-xe^u}+ [u^{n-1}] \frac{1}{1-x} \dfrac{e^{-\frac{xu}{1-x}}}{1-xe^u} $$$$$$
So we just need to focus on how to calculate $$$[u^{n}]\dfrac{e^{-\frac{xu}{1-x}}}{1-xe^u}$$$. Let $$$w=e^u-1$$$, we have: $$$$$$ [u^{n}] \dfrac{(w+1)^{-\frac{x}{1-x}}}{1-x(w+1)}\\ = \sum_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{(w+1)^{-\frac{x}{1-x}}}{1-x(w+1)}\\ = \sum_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-x(w+1)}\\ = \sum_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-xw-x}\\ = \dfrac{1}{1-x} \sum_{m=0}^n [u^n](e^u-1)^m[w^{m}] \dfrac{\sum_{i=0}w^i\binom{-\frac{x}{1-x}}{i}}{1-\frac{x}{1-x}w}\\ = \dfrac{1}{1-x} \sum_{m=0}^n [u^n](e^u-1)^m \sum_{i=0}^m \binom{-\frac{x}{1-x}}{i} (\dfrac{x}{1-x})^{m-i} $$$$$$
Let $$$s=\dfrac{x}{1-x}$$$ $$$$$$ = \dfrac{1}{1-x} \sum_{m=0}^n [u^n](e^u-1)^m \sum_{i=0}^m \binom{-s}{i} s^{m-i} $$$$$$ We know $$$[u^n](e^u-1)^m$$$ is the *Stirling numbers of the second kind*. We can calculate it in $$$O(n\log n)$$$ or $$$O(n \log^2 n)$$$. Let's build a $$$2 \times 2$$$ matrix to get $$$\sum_{i=0}^m \binom{-s}{i} s^{m-i}$$$. Let $$$M_m=\left[ \begin{matrix} \frac{-s-m}{m+1} & \frac{-s-m}{m+1}\\ 0 & s \end{matrix} \right]$$$. And we have $$$$$$ \left[ \begin{matrix} \binom{-s}{m} & \sum_{i=0}^m\binom{-s}{i}s^{m-i} \end{matrix} \right] \times \left[ \begin{matrix} \frac{-s-m}{m+1} & \frac{-s-m}{m+1}\\ 0 & s \end{matrix} \right] = \left[ \begin{matrix} \binom{-s}{m+1} & \sum_{i=0}^{m+1}\binom{-s}{i}s^{m+1-i} \end{matrix} \right] $$$$$$ So we can *divide and conquer* to calculate it in $$$O(n \log^2 n)$$$.
That's all. Best thanks for your great patience. This solution was proposed by Elegia. Without him, we would not create this problem. Great thanks to him.