概要
これリアルタイム参加したコンテストなんですが、当時は解法は分かっても構文解析書けないと思って取り組みませんでした。同じ解法をとった人、結構多いっぽいですが、「別解」だったみたいなので書いておきます。
解法
$$f(x)\equiv 0\pmod{10^K}\iff f(x)\equiv 0\pmod{2^K} \text{かつ} f(x)\equiv 0\pmod{5^K}$$ が成り立つことに注意します。
$f(x) \equiv 0\pmod{2^K}$ が成り立つ $x\in \Z/2^K\Z$ の全体を $\{a_1,a_2,\ldots,a_N\}$，$f(x) \equiv 0\pmod{2^K}$ が成り立つ $x\in \Z/5^K\Z$ の全体を $\{b_1,b_2,\ldots,b_M\}$ とすると、ある $i, j$ に対して $$x\equiv a_i\pmod{2^K} \text{かつ} x\equiv b_j\pmod{5^K}$$ となる $x\in \Z/10^K\Z$ の個数を求めることが課題です。
中国剰余定理より、$a_i, b_j$ を定めるとこのような $x$ は一意存在するので、答は $NM$ 個です。
つまり、$\pmod{2^K}$, $\pmod{5^K}$ の場合の同様の問題を解いて、答の積をとると、$\pmod{10^K}$ の場合の答が得られます。
これは計算量改善につながっています。
「すべての $x$ を試す」ことを前提として、構文解析と繰り返し二乗法による計算を行えば、計算量が $O(|S|10^K)$ から $O(|S|(5^K+2^K))$ へと変わっています。この方法により AC を得ることができます。
コメント
- 計算量解析で、繰り返し二乗法部分の $\log 10^K$ の類はつかないです。指数に $n$ 桁の <number> が乗ると、繰り返し二乗法には $O(\log 10^n) = O(n)$ 時間がかかります。これらは合計 $O(|S|)$ です。
- 解説手法と組み合わせると、$O(|S|5^{K/2}\text{poly}(K))$ になりそうですね。
- $x$ をベクトルとして扱う場合、$x$ をひとつも含まない文字列が入力である場合がコーナーケースとなります。
