問題
yukicoder Advent Calendar Contest 2021 C – A DELETEQ
（今回の目標は evil テストケースに対応することです。）
利用する典型テクニック
訂正：タイトルにある計算量を $O(x \log x)$ としていましたが、 $\bmod P$ 上の形式的べき級数 $( \bmod \ {\mathrm{x}^n} )$ の $M$ 乗を求めるアルゴリズムの計算量を $O( n \log P)$ として考えていることより誤りであったため、修正致しました。 (’22/1/16, ’22/1/25)
解説
通常制約の DP 解法
補助問題
AB が $x$ 個、 BA が $y$ 個、空文字列 $S$ がある。これを全て消費するまで次の操作を繰り返す。操作列の個数を $998244353$ で割った余りを求めよ。
- AB を $1$ 個消費して、 $S$ に AB と追記する。
- BA を $1$ 個消費して、 $S$ に BA と追記する。
- AB と BA $1$ 個ずつ消費して、 $S$ に AA と追記する。
- AB と BA $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$ を入れ替えて得られます。