yukicoder No.1964 sum = length - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の正整数列 ${A}$ のうち以下の条件を満たすもの数を求めよ．

${\sum_{i=1}^{N}A_i = N-1+\sum_{i=1}^{N}s(A_i)}$ ただし， ${s(x)}$ は ${x}$ を10進表記したものを文字列として見たときの長さ．

${1\leq N\leq 200}$

解説

要素を ${x}$ としたときの(スペースを含めた)長さと ${x}$ の差 ${t(x)(=x-s(x)-1)}$ は
${t(1)=1-s(1)-1=-1}$
${t(2)=2-s(2)-1=0}$
${t(3)=3-s(3)-1=1}$
${\cdots}$
${t(9)=9-s(9)-1=7}$
${t(10)=10-s(10)-1=}$ ${7}$
${\cdots}$
${t(99)=99-s(99)-1=96}$
${t(100)=100-s(100)-1=}$ ${96}$
${\cdots}$
${t(200)=200-s(200)-1=196}$
${\cdots}$
となる．
$[x^{-1}]\left(\sum_{i=1}^{N}x^{t(i)}\right)^N$ が答え．
${N\leq 200}$ に対しては
${\displaystyle [x^{-1}]\left(\sum_{i=1}^{N}x^{t(i)}\right)^N\\ \displaystyle=[x^{-1}]\left(\sum_{i=-1}^{\infty}x^i+x^7+x^{96}\right)^N\\ \displaystyle=[x^{N-1}]\left(\sum_{i=0}^{\infty}x^i+x^8+x^{97}\right)^N\\ \displaystyle=[x^{N-1}]\left(\frac{1+(x^8+x^{97})(1-x)}{1-x}\right)^N\\ \displaystyle=[x^{N-1}]\left(1+(x^8+x^{97})(1-x)\right)^N×\frac{1}{(1-x)^N}\\}$
であり， ${\displaystyle\left(1+(x^8+x^{97})(1-x)\right)^N}$ の ${N-1}$ 次までの係数は ${O(N)}$ で求められ， ${\displaystyle\frac{1}{(1-x)^N}=\sum_{i=0}^{\infty}\binom{N-1+i}{i}x^i}$ であるので，合計で ${O(N)}$ で求められる．一般には， $1+(x^8+x^{97})(1-x)$ の部分の項の数は ${O(\log{N})}$ であるので ${O(N\log{N})}$ かかる．FFTやNTTを使わないので定数倍はかなり良い(現在実行時間最速)．

提出プログラム

https://yukicoder.me/submissions/768594

問題概要

解説

提出プログラム

感想