SRM 428 - tsubosakaの日記

250

nextPermutationするだけ

500

解法は思いついたけど時間内にバグが取れなかった。まず高々k種類の文字列を用いて長さnまでの回文の合計を
$f(n,k)=\sum_{i=1}^n k^{(i+1)/2}$
とおく。つぎにちょうどk種類だけ用いて作れる回文の数をg(k)とかくと
$g(k) = f(n,k) - \sum_{j=1}^{i-1} {i \choose j} g(j)$
となる。求める解は
$\sum_{i=1}^k {26 \choose i} g(i)$
となる。
行列乗算でやる方法の方が素直だと思う.

1000

読んでない

追記:一部記号ミスを訂正