9011: FFT Prohibited?
[만든사람 : 10hour]
문제 설명
길이 n짜리 다항식 2개를 빠르게 곱하는건 고속 푸리에 변환으로 빠르게 처리할 수 있다.
그러나 출제진이 그런 정신나간 문제를 낼 리는 없다.
대신 여러분은 길이 2짜리 다항식을 n번 곱하면 된다.
입력 설명
첫 번째 줄에 다항식을 곱할 횟수 $n$이 입력된다. $(1\leq n \leq 100)$
두 번째 줄에 $A+Bx$ 꼴 다항식의 계수 $A$, $B$가 입력된다. $(-1000 \leq A,\ B \leq 1000)$
두 번째 줄에 $A+Bx$ 꼴 다항식의 계수 $A$, $B$가 입력된다. $(-1000 \leq A,\ B \leq 1000)$
출력 설명
첫 번째 줄에 0차항부터 n차 항까지 공백으로 구분하여 출력한다.
수가 커질 수 있으므로 각 항을 $998244353$으로 나눈 나머지를 대신 출력한다.
수가 커질 수 있으므로 각 항을 $998244353$으로 나눈 나머지를 대신 출력한다.
입력 예시 Copy
4
1 1
출력 예시 Copy
1 4 6 4 1
도움
이항계수의 점화 관계는 다음과 같이 표현할 수 있다.
$$
\binom{n}{k}=\begin{cases}\binom{n-1}{k-1}+\binom{n-1}{k} & \text{if } 0<k<n\\1 & \text{if } k=0 \text{ or } k=n\end{cases}
$$
$$
\binom{n}{k}=\begin{cases}\binom{n-1}{k-1}+\binom{n-1}{k} & \text{if } 0<k<n\\1 & \text{if } k=0 \text{ or } k=n\end{cases}
$$