Official

H - Incomplete Notes Editorial by hitonanode


\(1 \le i \le N - M + 1\) をみたす各整数 \(i\) に対して、変数 \(t\) を引数とする関数 \(f_i(t)\) を以下のように定義します:

\[ f_i (t) = \sum_{j = 1}^M (A_{i + j - 1} - t B_j)^2 \mathbf{1}(A_{i + j - 1} > 0) \mathbf{1}(B_j > 0). \]

ただし、\(\mathbf{1}(x)\) を「命題 \(x\) が真のとき \(1\)、偽のとき \(0\) を返す関数」とします。各 \(i\) について、 \(f_i (t) = 0\) が正の実数解を持つならば、この \(t\) を使用して実際に条件を満たす \(B, C\) を構築できます。

\(i\) に対する \(f_i (t)\) の具体的な形を高速に求めることを考えます。右辺は、二乗の部分を展開することで線形畳み込みに帰着されます。\(f_i (t)\) は各 \(i\) について \(t\)\(2\) 次関数となり、各項の係数は絶対値が \(2.5 \times 10^{17}\) 以下の整数です。よって、\(p = 119 \times 2^{23} + 1\)\(p = 441 \times 2^{21} + 1\) などの複数の素数 \(p\) について \(\mathbb{F}_p\) 上で数論変換(NTT)を用いて畳み込みを行なった上で Garner のアルゴリズム等を用いることで \(f_i (t)\) の各項の係数を復元できます。

あとは、\(f_i(t) = 0\) が正の実数解を持つ \(i\) の個数を求めれば良いです(なお \(f_i(t)\) の定義から、 \(f_i(t)\)\(t\)\(2\) 次関数で \(f_i (t) = 0\) が実数解を持つならば、これは必ず正の重解になることがわかります)。これには 128 ビット整数型を用いて二次方程式 \(f_i(t) = at^2 + bt + c = 0\) の解の判別式 \(D = b^2 - 4ac\) を直接計算しても良いですし、大きい素数 \(p\) を複数個取って \(\mathbb{F}_p\) 上で \(D\) を繰り返し計算して確かめても良いです。

上記の解法における計算量のボトルネックは長さ \(O(N)\) の数列に対する畳み込み(想定解では 6 回)で、想定計算量は \(O(N \log N)\) です。

posted:
last update: