시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 40 | 25 | 6 | 50.000% |
Mathematician Pang learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special.
If $f,g: \{1,2,\ldots,n\} \to \mathbb {Z} $ are two functions from the positive integers to the integers, the Dirichlet convolution $f * g$ is a new function defined by: $$(f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}}) .$$
We define the $k$-th power of an function $g=f^k$ by $$ f^{k}=\underbrace {f * \dots * f} _{k {\textrm {times}}}.$$
In this problem, we want to solve the inverse problem: Given $g$ and $k$, you need to find a function $f$ such that $g=f^k$.
Moreover, there is an additional constraint that $f(1)$ and $g(1)$ must equal to $1$. And all the arithmetic operations are done on $\mathbb{F}_{p}$ where $p=998244353$, which means that in the Dirichlet convolution, $(f * g)(n) =\left(\sum_{d \mid n}f(d)g ({\frac {n}{d}})\right) \bmod p$.
The first line contains two integers $n$ and $k (2\leq n\leq 10^5,1\leq k<998244353)$ .
The second line contains n integers $g(1), g(2),..., g(n)$ ($0\le g(i)<998244353, g(1)=1$).
If there is no solution, output $-1$.
Otherwise, output $f(1), f(2), ..., f(n)$ ($0\le f(i)<998244353, f(1)=1$). If there are multiple solutions, print anyone.
5 2 1 8 4 26 6
1 4 2 5 3