No.3172 Fourier Series Expansion of Powers of a Trigonometric Function
Problem Statement
Expand the $N$-th power of the cosine function ($\cos ^{N} x$) for $x \in \mathbb{R}$ into a linear expression in the cosines of non-negative integer multiples of the angle ($\cos kx$, $0 \leq k \leq N$), and find the value of each term's coefficient multiplied by $2^{N}$, modulo $\bmod\,998244353$.
That is, when
$$
(2 \cos x ) ^ {N} = \sum\limits_{k = 0}^{N} b_{k} \cos (kx)
=b_{0}+b_{1}\cos x+b_{2}\cos 2x + b_{3}\cos 3x+ \cdots + b_{N}\cos (Nx)
$$
find each element of the coefficient sequence $(b_{0}, b_{1}, b_{2}, \cdots, b_{N})$ modulo $\bmod\,998244353$.
It can be shown that under the constraints of this problem the coefficients are always integers. It can also be shown that such an expansion exists and is unique.
Hint
The cosine function \(\cos x\) has the following properties.
- $\cos(x) = \cos(-x)$
- For arguments $A$, $B$ of the cosine function,
$\cos (A)\cos (B)={\displaystyle{\frac{\cos (A-B) + \cos (A+B)}{2}}}$
Input
$N$
- $0 \leq N \leq 2\times 10^{5}$
- The input is an integer.
Output
Let $(b_{0}, b_{1}, b_{2}, \cdots, b_{N})$ be the coefficient sequence taken modulo $\bmod\,998244353$. Output it in the following format. Print a newline at the end.
$b_{0}$ $b_{1}$ $b_{2}$ $\cdots$ $b_{N}$
Sample
Sample 1
Input
2
Output
2 0 2
From the half-angle formula or similar, we get $(\cos x)^{2} = {\displaystyle\frac{1 + \cos 2x}{2}}$. Multiplying this by $2^{2}$ gives $$ (2\cos x)^{2} = 2 + 0 \cos x + 2 \cos 2x $$ Output the coefficient sequence $(2, 0, 2)$.
Sample 2
Input
0
Output
1
When $N = 0$, we have $(2\cos x)^{0} = 1$, so output its coefficient sequence $(1)$.
Sample 3
Input
3
Output
0 6 0 2
The triple-angle formula and the like give the well-known identity $\cos 3x = 4 \cos^{3} x - 3 \cos x$. Rearranging this identity, we find that $$ (2 \cos x)^{3} = 0 + 6 \cos x + 0 \cos 2x + 2 \cos 3x $$ Output the coefficient sequence $(0, 6, 0, 2)$.
Sample 4
Input
10
Output
252 0 420 0 240 0 90 0 20 0 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen