部分点解法とその考察

? を (, ) の数が同じになるように、前半を ( 後半を ) に置き換えて、括弧列になることと、良い文字列であることは同値です。

(?()(??)??
 (   () ))
((()(())))

ここで、操作を逆に考えます。括弧列に対して \(1,2,\dots 2N\) 文字目の順に以下の操作のいずれかを行います。

• 操作 \(1\) ( を ? に置き換える

• 操作 \(2\) ) を ? に置き換える

• 操作 \(3\) 何もしない

ただし、操作 \(2\) を行うと操作 \(1\) を行うことができなくなります。

全ての括弧列に対する、置き換え方の場合の数の和を求めれば良いです。

ここで、カタラン数の母関数を \(C(x)\) とします

操作 \(1\) を行わない置き換え方は全ての文字列について \(2^{N}\) 通りなので、括弧列と置き換え方の組の場合の数は \(2^{N}([x^{N}]C(x))\) 通りです。

操作 \(1\) を最後に行ったときに、元の括弧列について ( の今まで登場した数が ) より \(j\; (1\leq j\leq N)\) 個多いような、括弧列と置き換え方の組の場合の数は \(2^{N+j-1}([x^{N-j}]C^{2j+1}(x))\) 通りです。

なぜこの式になるかの説明をします。

最後に操作 \(1\) を行うまでに出てきた ) の数を \(k\) とすると、最後に操作 \(1\) を行うまでに出てきた ( の数は \(j+k\) 個で、その後出てくる ) の数は \(N-k\) 個になります。

この \((j+k)+(N-k)=N+k\) 個は ? に置き換えることができる文字で、そのうち \(1\) 文字は ? に置き換えることが確定しているので、置き換え方は \(2^{N+j-1}\) 通りとなります。

\([x^{N-j}]C^{2j+1}(x)\) については、最後に操作 \(1\) を行った文字より前にある ( の数が ) の数より \(j-1\) 個多くて、後ろにある ) の数が ( の数より \(j\) 個多いので、このようになります。

任意の正整数 \(n,d\) について \(([x^{n}]C^{d}(x))=\dfrac{d}{n}\left( \begin{matrix} d+2n-1\\ n-1\\ \end{matrix} \right)\) が成り立ちます。

参考 https://maspypy.com/多項式・形式的べき級数-高速に計算できるもの#toc47

よって階乗などを前計算することで、時間計算量 \(O(N)\) で求めることができます。

部分点実装例 https://atcoder.jp/contests/ttpc2023/submissions/45541844

ここまでが部分点の解説です。

P-recursive であることの説明

カタラン数が P-recursive であることからこの答えも P-recursive であるのではという予想が立ちます。

実際に P-recursive であることを示します。

参考 https://atcoder.jp/contests/abc222/editorial/2742

\(a_{i}\) を \(N=i\) としたときの答え (\(a_{0}=1\) とする)、\(b_{i}=\frac{a_{i}}{2^{i}}\) 、\(c_{n}=[x^{n}]C(x)\) とし、\(f(x)=\sum b_{i}x^{i}\) とすると、上の考察より、以下が成り立ちます。

(\(C(x),f(x)\) は \(C,f\) と省略します)

\[f=C＋\dfrac{C^{3}x}{1-2xC^{2}}\]

\(xC^{2}=C-1\) より、

\[f=C\left(1+\dfrac{C-1}{3-2C}\right)\]

\[f=C\left(\dfrac{2-C}{3-2C}\right)\]

\(C=\dfrac{1-\sqrt{1-4x}}{2x}\) より、

\[C\left(\dfrac{2-C}{3-2C}\right)=\dfrac{C}{2}\left(\dfrac{4x-(1-\sqrt{1-4x})}{3x-(1-\sqrt{1-4x})}\right)=\dfrac{C}{2}\left(\dfrac{12x-3-\sqrt{1-4x}}{9x-2}\right)=\dfrac{C}{2}\left(\dfrac{12x-3+2xC-1}{9x-2}\right)=\dfrac{C(6x-2)+xC^{2}}{9x-2}=\dfrac{C(6x-1)-1}{9x-2}\]

よって、

\[(9x-2)f=C(6x-1)-1\]

非負整数 \(n\) を用いて、 \(x^{n+1}\) の項に注目すると、

\[9b_{n}-2b_{n+1}=6c_{n}-c_{n+1}\]

\((4n+2)c_{n}=(n+2)c_{n+1}\) より、

\[9b_{n}-2b_{n+1}=c_{n}\left(6-\dfrac{4n+2}{n+2}\right)\]

\(x^{n+2}\) の項にも注目すると、

\[9b_{n+1}-2b_{n+2}=c_{n+1}\left(6-\dfrac{4n+6}{n+3}\right)\]

\[9b_{n+1}-2b_{n+2}=c_{n}\left(\dfrac{4n+2}{n+2}\right)\left(6-\dfrac{4n+6}{n+3}\right)\]

よって、

\[(9b_{n}-2b_{n+1})\left(\dfrac{4n+2}{n+2}\right)\left(6-\dfrac{4n+6}{n+3}\right)=(9b_{n+1}-2b_{n+2})\left(6-\dfrac{4n+6}{n+3}\right)\]

この式を展開し、さらに \(a_{n}\) の式に変更すると、以下が成り立ちます。

\[a_{n}(72n^{2}+468n+216)+a_{n+1}(-17n^{2}-124n-159)+a_{n+2}(n^{2}+8n+15)=0\]

よって、 \((a_{0},a_{1},\dots)\) は P-recursive であることが説明されました。

P-recursive な数列の計算方法

\((a_{0},a_{1},\dots)\) は P-recursive で、任意の非負整数 \(i\) に対して \(a_{i}f_{2}(i)+a_{i+1}f_{1}(i)=a_{i+2}f_{0}(i)\) を満たす \(2\) 次の多項式の列 \(f_{0}(i),f_{1}(i),f_{2}(i)\) が存在します。

そのような数列の \(N\) 項目は時間計算量 \(O(\sqrt{N}\log{N})\) で計算できます。

Nyaan さんの記事を大いに参考しています。

https://nyaannyaan.github.io/library/fps/find-p-recursive.hpp

行列で表す

\(A(i,j)=a_{i}\prod_{k=0}^{j-1}f_{0}(k)\) とします。 すると、以下の式が成り立ちます。

• \(A(i+2,i+1)=f_{1}(i)A(i+1,i)+f_{2}(i)A(i,i)\)

• \(A(i+1,i+1)=f_{0}(i)A(i+1,i)\)

よって、 \(P_{i}=(A(i,i),A(i+1,i))\) がわかっていれば、 \(P_{i+1}\) を求めることができます。

\(A(i,i)=a_{i}\prod_{k=0}^{i-1}f_{0}(k)\) より、 \(a_{N}=\dfrac{A(N,N)}{\prod_{k=0}^{N-1}f_{0}(k)}\)

となるため、 \(P_{N},\prod_{k=0}^{N-1}f_{0}(k)\) が分かれば良いです。

ただし、\(\prod_{k=0}^{i-1}f_{0}(k)\equiv 0 \pmod{M}\) のとき、計算することが不可能になってしまいますが、今回は \(f_{0}(k)=(k+3)(k+5)\) かつ、 \(M-N\geq 11\) より問題ありません。( \(9\times 10^{8}\) 以上の最小の素数が \(9\times 10^{8}+11\) であることより )

\[ P_{N}=P_{0} \left( \begin{matrix} 0 & f_{2}(0)\\ f_{0}(0) & f_{1}(0)\\ \end{matrix} \right) \left( \begin{matrix} 0 & f_{2}(1)\\ f_{0}(1) & f_{1}(1)\\ \end{matrix} \right) \cdots\left( \begin{matrix} 0 & f_{2}(N-1)\\ f_{0}(N-1) & f_{1}(N-1)\\ \end{matrix} \right) \]

より、多項式を要素にもつ行列の変数に \(0,1,\dots N-1\) を代入した値を順番にかけた値が分かればいいです。

\( \prod_{k=0}^{N-1}f_{0}(k)\) の求め方

この解説では \( \prod_{k=0}^{N-1}f_{0}(k) \) の計算方法のみ紹介します。その方法は簡単に行列に拡張することができるのでもう一方は省略します。

ある整数定数 \(a\) が存在するとして、任意の \(i\) について、 \(\prod_{k=0}^{2^{a}-1}f_{0}(k+i2^{a})\) が求まれば、 \(O(\frac{N}{2^{a}}+2^{a})\) で求めることができます。

\(f_{0}(k)\) が \(d\) 次式だとして、この \(a\) を \(d4^{a}\) が \(N\) 以上となるようにできるだけ小さく取ります。すると、\(d(=2)\) が定数であることから、\(\prod_{k=0}^{2^{a}-1}f_{0}(k+i2^{a})\) が求まっていれば \(O(\sqrt{N})\) で求めることができます。

\(\prod_{k=0}^{2^{a}-1}f_{0}(k+i2^{a})\)　を \(i\) の十分大きい範囲で求めることを目指します。

まず、 整数 \(0\leq i\leq d\) について \(f_{0}(i2^{a})\) を求めます。

ある非負整数 \(w\) について、任意の整数 \(0\leq i\leq d2^{w}\) に対する以下の式の値がわかっているとします。

• \(\prod_{k=0}^{2^{w}-1}f_{0}(k+i2^{a})\)

この式の値から任意の整数 \(0\leq i\leq d2^{w}\) に対する下の \(3\) つの式の値が計算できたとします。

• \(\prod_{k=0}^{2^{w}-1}f_{0}(k+i2^{a}+2^{w})\)
• \(\prod_{k=0}^{2^{w}-1}f_{0}(k+i2^{a}+d2^{w+a})\)
• \(\prod_{k=0}^{2^{w}-1}f_{0}(k+i2^{a}+d2^{w+a}+2^{w})\)

任意の整数 \(0\leq i\leq d2^{w+1}\) に対する \(\prod_{k=0}^{2^{w+1}-1}f_{0}(k+i2^{a})\) の値がわかります。

今 \(w=0\) における式の値がわかっているので、これをひとつずつ進めて \(w=a\) について計算できれば良いです。

\(\prod_{k=0}^{2^{w}-1}f_{0}(x)\) が \(d2^{w}\) 次式であることから、以下を満たす \(d2^{w}\) 次多項式 \(g(x)\) が存在します。

• 任意の \(0\leq i\leq d2^{w}\) について、\(g(i)= \prod_{k=0}^{2^{w}-1}f_{0}(k+i2^{a})\)

よって、任意の整数 \(0\leq i\leq d2^{w}\) について、以下の \(3\) つがわかれば良いです。

• \(g(i+\frac{2^{w}}{2^{a}})\)
• \(g(i+d2^{w})\)
• \(g(i+d2^{w}+\frac{2^{w}}{2^{a}})\)

これは Shift of Sampling Points of Polynomial という Library Checker にのっている問題と同値で、それぞれ \(O(d2^{w}\log{(d2^{w})})\) で求めることができます。

https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial

法が入力で与えられるとしても、この問題を解く方法と同じ方法で \(g(i+\frac{2^{w}}{2^{a}})\) などを求めることができるので、この問題の解き方を紹介します。

Shift of Sampling Points of Polynomial の解き方

ここでは、 変数の名前は Library Checker に合わせています。 また、今までの変数と同じ名前の変数が出てくるかもしれませんが、リセットされていると考えてください。

次数 \(N\) 未満の多項式　\(f(x)\) について、 \(f(0),f(1),\dots ,f(N-1)\) の値がわかっています。 \(i=0,1,\dots ,M-1\) に対して \(f(i+c)\pmod{998244353}\) で求めてください。

元問題では法が \(998244353\) ですが、 法が \(10^{9}\) 程度の大きさの素数であっても任意 mod 畳み込みを用いることで同様に答えを求めることができます。

ラグランジュ補間の式より、

\[f(x)=\sum_{k=0}^{N-1}f(k)\prod_{j\neq k}\frac{x-j}{k-j}\]

ここで、任意の \(0\leq j\lt N\) と \(0\leq k\lt M\) について、\(k+c-j\) が \(998244353\) の倍数でない場合を考えます。

(\(k+c-j\) が \(998244353\) の倍数であるような \(k,c,j\) が存在する場合でも、存在しない場合にうまく帰着することができます。)

すると、任意の整数 \(c\leq i\lt c+M\) について以下が成り立ちます。

\[f(i)=\left(\prod_{j=0}^{N-1}(i-j)\right)\sum_{k=0}^{N-1}\left(\dfrac{f(k)}{(i-k)\cdot k!\cdot (N-k-1)!\cdot (-1)^{k}}\right)\]

\(\displaystyle \prod_{j=0}^{N-1}(i-j)\) については全ての \(c\leq i\lt c+M\) について \(O(N+M+\log{MOD})\) で求めることができます。

下記のように \(F,G,H\) をおきます。

\[\sum_{k=0}^{N-1}\dfrac{f(k)}{k!\cdot (N-k-1)!\cdot (-1)^{k}}\cdot x^{k}\]

\[\displaystyle H(x)=\sum_{k=0}^{M+N-2} \dfrac{1}{c-(N-1)+k} \cdot x^{k}\]

\[F(x)=G(x)H(x)\]

任意の整数 \(c\leq i\lt c+M\) について以下が成り立ちます。

\[f(i)=\left(\prod_{j=0}^{M-1}(i-j)\right)\left([T^{i-c+N-1}]F(T)\right)\]

\(c\leq i\lt c+M\) について \(f(i)\) が求まりました。

時間計算量は \(F(x)=G(x)H(x)\) の部分がボトルネックとなって \(O(N+M\log{(N+M)})\) になります。

計算量

以上を組み合わせることで \(\prod_{k=0}^{N-1}f_{0}(k)\) が求められ、同じ方法で \(A(N,N)\) を求められます。

時間計算量は \(w=a-1\) のときに長さが \(2^{w}\) の Shift of Sampling Points of Polynomial を解く部分がボトルネックとなって \(O(\sqrt{N}\log{N})\) となります。

満点実装例 https://atcoder.jp/contests/ttpc2023/submissions/46452363