No.3172 三角関数べき乗のフーリエ級数展開
タグ : / 解いたユーザー数 51
作問者 :
t98slider
/ テスター :
37zigen
問題文
$x \in \mathbb{R}$における余弦関数の $N$ 乗 ($\cos ^{N} x$) を、余弦関数の非負整数倍角 ($\cos kx$, $0 \leq k \leq N$) の一次式に展開し、各項の係数を $2^{N}$ 倍した値を $\bmod\,998244353$ で求めて下さい。
すなわち、
$$
(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)
$$
とした際の係数列 $(b_{0}, b_{1}, b_{2}, \cdots, b_{N})$ をそれぞれ $\bmod\,998244353$ で求めてください。
なお本問題の制約下では係数は必ず整数になることが示せます。また、このような展開が存在して、一意であることが示せます。
ヒント
余弦関数 \(\cos x\) には以下の性質が成り立ちます。
- $\cos(x) = \cos(-x)$
- $A$, $B$ を余弦関数の変数として
$\cos (A)\cos (B)={\displaystyle{\frac{\cos (A-B) + \cos (A+B)}{2}}}$
入力
$N$
- $0 \leq N \leq 2\times 10^{5}$
- 入力は整数
出力
係数列を $\bmod\,998244353$ としたものを $(b_{0}, b_{1}, b_{2}, \cdots, b_{N})$ とするとき以下の形式で出力してください。 最後に改行してください。
$b_{0}$ $b_{1}$ $b_{2}$ $\cdots$ $b_{N}$
サンプル
サンプル1
入力
2
出力
2 0 2
半角の公式などから $(\cos x)^{2} = {\displaystyle\frac{1 + \cos 2x}{2}}$ が得られます。これを $2^{2}$ 倍すると、 $$ (2\cos x)^{2} = 2 + 0 \cos x + 2 \cos 2x $$ が得られます。これらの係数列である $(2, 0, 2)$ を出力します。
サンプル2
入力
0
出力
1
$N = 0$ のときは $(2\cos x)^{0} = 1$ となるため、これの係数列である $(1)$ を出力します。
サンプル3
入力
3
出力
0 6 0 2
三倍角の公式などで $\cos 3x = 4 \cos^{3} x - 3 \cos x$ が知られています。 この式を変形すると、 $$ (2 \cos x)^{3} = 0 + 6 \cos x + 0 \cos 2x + 2 \cos 3x $$ となることが分かります。係数列である $(0, 6, 0, 2)$ を出力します。
サンプル4
入力
10
出力
252 0 420 0 240 0 90 0 20 0 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。