yukicoder A DELETEQ $O(x \log P)$ (’22/1/16 計算量修正)

問題

yukicoder Advent Calendar Contest 2021 C – A DELETEQ

(今回の目標は evil テストケースに対応することです。)

No.1771 A DELETEQ - yukicoder
競技プログラミングの練習サイト

利用する典型テクニック

訂正:タイトルにある計算量を $O(x \log x)$ としていましたが、 $\mathbb{Z}_P$ 上の形式的べき級数 $( \bmod \ {\mathrm{x}^n} )$ の $M$ 乗を求めるアルゴリズムの計算量を $O( n \log P)$ として考えていることより誤りであったため、修正致しました。 (’22/1/16)

解説

通常制約の DP 解法

補助問題

AB が $x$ 個、 BA が $y$ 個、空文字列 $S$ がある。これを全て消費するまで次の操作を繰り返す。操作列の個数を $998244353$ で割った余りを求めよ。

  • AB を $1$ 個消費して、 $S$ に AB と追記する。
  • BA を $1$ 個消費して、 $S$ に BA と追記する。
  • ABBA $1$ 個ずつ消費して、 $S$ に AA と追記する。
  • ABBA $1$ 個ずつ消費して、 $S$ に BB と追記する。

$(y,x)=(n,m)$ のときの補助問題の答えを $\mathrm{dp}[n][m]$ と表します。

$\begin{aligned}\mathrm{dp}[n][m]=\mathrm{dp}[n-1][m]+\mathrm{dp}[n][m-1]+2\mathrm{dp}[n-1][m-1]\end{aligned}$

貰う DP を表す漸化式です。

元の問題の答え $Q$ は

$\begin{aligned}Q=\sum_{k=0}^{\min\{x,y\}}\mathrm{dp}[x-k][y-k]\end{aligned}$

と表せます。

詳細には、 writer による解説をご覧ください。

$\mathrm{dp}[y]$ を求める

$ \begin{aligned} \sum_{i=0}^{\infty}\mathrm{dp}[y][i]\mathrm{x}^i=\frac{1}{1-\mathrm{x}}\left( \frac{1+2\mathrm{x}}{1-\mathrm{x}} \right) ^y \end{aligned} $

(2021年12月26日:漸化式修正)DP 解法の漸化式は、 $\mathrm{dp}\prime[n][m]=2 \times \mathrm{dp}[n-1][m-1]+\mathrm{dp}[n-1][m]\hspace{5px}(0 \leq m)$ を計算してそれの累積和をとったものと言えます。

累積和は形式的冪級数でいうところの $\frac{1}{1-\mathrm{x}}$ の乗算にあたるので、計算の過程は

$\begin{aligned}\sum_{i=0}^{\infty}\mathrm{dp}[n][i]\mathrm{x}^i=\frac{1+2\mathrm{x}}{1-\mathrm{x}}\sum_{i=0}^{\infty}\mathrm{dp}[n-1][i]\mathrm{x}^i\end{aligned}$

となります。ここで初期状態は

$\begin{aligned}\mathrm{dp}[0][i]=1\end{aligned}$

つまり

$\begin{aligned}\sum_{i=0}^{\infty}\mathrm{dp}[0][i]\mathrm{x}^i=\frac{1}{1-\mathrm{x}}\end{aligned}$

です。以上から、緑枠の式が求まります。

答えを求める

$\begin{aligned}f[y](\mathrm{x}):=\sum_{i=0}^{\infty}\mathrm{dp}[y][i]\mathrm{x}^i\end{aligned}$

$\begin{aligned}g(\mathrm{x}):=\frac{1+2\mathrm{x}}{1-\mathrm{x}}\end{aligned}$

とおきます。

対称性より、あらかじめ $x\lt y$ としておくことができ、このとき問題の答え $Q$ は

$\begin{aligned}Q=[\mathrm{x}^x]\left(\frac{f[y](\mathrm{x})}{1-\frac{\mathrm{x}}{g(\mathrm{x})}}\right)\end{aligned}$

と表せます。

これは次の式変形から求まります。

$$\begin{aligned}Q&= \sum_{k=0}^{x}[\mathrm{x}^{x-k}]\left(f[y-k](\mathrm{x})\right) \\ &= [\mathrm{x}^{x}]\sum_{k=0}^{x}\left(\mathrm{x}^kf[y-k](\mathrm{x})\right) \\ &= [\mathrm{x}^{x}]\sum_{k=0}^{x}\left\{\left(\frac{\mathrm{x}}{g(\mathrm{x})}\right)^kf[y](\mathrm{x})\right\}\\ &= [\mathrm{x}^{x}]\left\{f[y](\mathrm{x})\sum_{k=0}^{\infty}\left(\frac{\mathrm{x}}{g(\mathrm{x})}\right)^k\right\}\\ &= [\mathrm{x}^x]\left(\frac{f[y](\mathrm{x})}{1-\frac{\mathrm{x}}{g(\mathrm{x})}}\right) \end{aligned}$$

ちなみに、問題の解説ページにリンクがある hitonanode さんの解説にある式は、この式の $x$ と $y$ を入れ替えて得られます。

解答例

タイトルとURLをコピーしました