No.665
タイトルの通り, ベルヌーイ数を求めてそこから計算する.
ベルヌーイ数の求め方は以下の通り.
\[B_0 = 1 \\ B_n = -\frac{1}{n+1}\sum_{k=0}^{n-1}\binom{n+1}{k}B_k\]ベルヌーイ数を求めた後, 和は以下の式で計算できる.
\[\begin{align} S_k(n) &= \sum_{j=0}^{n-1} n^k \\ &= \frac{1}{k+1}\sum_{j=0}^k\binom{k+1}{j}B_jn^{k-j+1} \end{align}\]二項係数を計算するために階乗と逆元はあらかじめ計算しておく.
これでも時間はギリギリなので, 奇数番目のベルヌーイ数は0になることを利用して計算を省くなりしないと通らなかった.