|
||||||||||
Find the Number of PathsTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 221 Accepted Submission(s): 59 Problem Description Huah has $n+k$ cities numbered $1,2,.... ,n+k$, the city $i(1\le i< n+k)$ to the city $i+1$ has $n+k-i$ distinct one-way roads. For each $x=1,2,...,n-1$,the city $i(x< i\le n+k)$ to the city $i-x$ has $a_x$ distinct one-way roads. For $m=k+1,k+2,... ,k+n$,find the number of paths from city $k+1$ to city $m$ that pass through exactly $k$ number of roads. Two paths are distinct when and only if the sequence of edges they pass through is distinct and the answer is modulo $998244353$. Input First line has one integer $T(1\le T\le 14)$, indicating there are $T$ test cases. In each case: First line input two integers $n,k(2\le n\le 2\times 10^5,1\le k\le 2\times 10^5)$. Second line $n-1$ integers $a_1,a_2,... ,a_{n-1}(0\le a_i\le 998244352)$. There is a blank line between case $i(1\le i< T)$ and case $i+1$. Input guarantee $\sum (n+k) \le 1006769$. Output In each case, output a row of $n$ integers with the $i$-th integer being the answer when $m=k+i$. Sample Input
Sample Output
Source | ||||||||||
|