かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

yukicoder No.269 見栄っ張りの募金活動

yukicoder 典型 解説 競技プログラミング 数え上げ 形式的冪級数

問題はこちら

問題概要

長さ{N}の数列{A}であって，以下の条件を満たすものの数を求めよ．

  • 数列の総和が{S}
  • {A_{i-1}+K\leq A_i (2\leq i\leq N)}
  • {0\leq A_1}

{2\leq N\leq 100\\ 0\leq S\leq 20000\\ 0\leq K\leq 100}

解説

{A_0=0}とし，{A_i-A_{i-1}=d_i}とすると，

  • {K\leq d_i(2\leq i\leq N)}
  • {0\leq d_1}
  • {\displaystyle\sum_{i=1}^{N}(N+1-i)d_i=S}

となる{d_i(1\leq i\leq N)}の組の数が答えとなる．

{\displaystyle[x^S]\frac{1}{1-x^N}\times\prod_{i=1}^{N-1}\frac{x^{Ki}}{1-x^i}\\ \displaystyle =[x^{S-\frac{KN(N-1)}{2}}]\prod_{i=1}^{N}\frac{1}{1-x^i}}

したがってDPにより{O(NS)}で求められる．
{O(S\log{S})}で求めることもできる．

kanpurin.hatenablog.com

提出プログラム

https://yukicoder.me/submissions/708237

感想