かんプリンの学習記録

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

TDPC F - 準急

形式的冪級数 競技プログラミング 解説

形式的冪級数を用いた解法です．

問題はこちら

問題概要

ある路線には駅{1}から駅{N}までの{N}個の駅がある．準急は駅{1}に止まり，{駅{2,\cdots ,}駅{N-1} }の部分集合に止まり，駅{N}に止まる．連続する{K}個以上の駅に止まると，客が飽きてしまうので，そのようなことはしない．

{2\leq K\leq N\leq 10^6}

解説

{i}番目に止まる駅を{a_i}とする({a_1=1,a_L=N}，{L}は止まる駅の数)．{b_i=a_{i+1}-a_i}で表される数列{b}として次の条件を満たすものの数を数える問題となる．

  • {1\leq b_i}
  • {\displaystyle\sum_{i=1}^{L-1}b_i=N-1}
  • {b_i=b_{i+1}=\cdots =b_{i+K-2}=1}となる{i(1\leq i\leq L-K)}が存在しない．

{b}の構造として「{0}回以上{K-2}回以下の{b_i=1}」と「{1}回の{2\leq b_i}」が交互にくる．最初と最後は「{0}回以上{K-2}回以下の{b_i=1}」でなければならない．

{\begin{eqnarray}\displaystyle f&=&\left(\sum_{i=0}^{K-2}x^i\right)\cdot\left(\sum_{i=2}^{\infty}x^i\right)\\ \displaystyle &=&\frac{1-x^{K-1}}{1-x}\cdot\frac{x^2}{1-x}\\ \displaystyle &=&\frac{x^2(1-x^{K-1})}{(1-x)^2} \end{eqnarray}}として
{\displaystyle [x^{N-1}]\sum_{i=0}^{\infty}f^i\sum_{j=0}^{K-2}x^j}が答えとなる．
{\displaystyle \sum_{i=0}^{\infty}f^i\sum_{j=0}^{K-2}x^j\\ \displaystyle =\frac{1}{1-f}\cdot\frac{1-x^{K-1}}{1-x}\\ \displaystyle =\frac{1}{1-\frac{x^2(1-x^{K-1})}{(1-x)^2}}\cdot\frac{1-x^{K-1}}{1-x}\\ \displaystyle =\frac{1-x-x^{K-1}+x^K}{1-2x+x^{K+1}}\\}

したがって{\displaystyle[x^{N-1}]\frac{1-x-x^{K-1}+x^K}{1-2x+x^{K+1}}}が答え．
分母は次数は大きいが，疎な多項式であるので，{A_{n}=2A_{n-1}-A_{n-K-1}}という漸化式になりDPで解ける{O(N)}．
また，Bostan–Moriのアルゴリズムを用いると{O(K\log{K}\log{N})}でも解ける(定数倍重め)．

提出プログラム

https://atcoder.jp/contests/tdpc/submissions/27595085

感想