◆漸化式

正の整数 \(n, x\) に対して、第 \(n\) 項から始まる整数列 \(X = (X_n, \ldots, X_{N+1})\) であって、\(i\geq n\) に対して問題の条件を満たすもののうち、\(X_n = x\) を満たすものの個数を \(\text{dp}_n(x)\) と書くことにします。このとき、\(\text{dp}_n(x)\) は以下の漸化式によって、\(n = N+1, N, \ldots, 1\) の順に定まります。

• \(\text{dp}_{N+1}(x) = \begin{cases}1 & (1\leq x\leq M)\\0 & (M < x)\end{cases}\)
• \(\text{dp}_n(x) = \sum_{A_nx\leq y}\text{dp}_{n+1}(y)\)

答は \(\sum_{x} \text{dp}_1(x)\) です。しかし \(M\) は巨大で、個々の \(x\) に対して \(\text{dp}_i(x)\) の値を直接計算する方法では解くことはできません。

---

◆\(\text{dp}_i\) と多項式

\(i = N+1, N, \ldots, 1\) に対して帰納的に、次の条件を満たす整数 \(R_i\) および多項式 \(f_i, F_i\) の存在を証明できます。

• \(x > R_i\) ならば \(\text{dp}_i(x) = 0\)
• \(f_i\) は \(N+1-i\) 次多項式で、\(1\leq x\leq R_i\) に対して \(\text{dp}_i(x) = f_i(x)\) を満たす
• \(F_i\) は \(N+2-i\) 次多項式で、\(0\leq x\leq R_i\) に対して \(\sum_{1\leq y \leq x}\text{dp}_i(y) = F_i(x)\) を満たす

そこで、\(\text{dp}_i(x)\) のテーブルを持つかわりに、\(R_i, f_i, F_i\) を持つことにしましょう。

---

◆データの持ち方・計算方法

多項式 \(f_i\) と同等なデータを管理する方法はいくつか考えられますが、ここでは次の値を管理することにします（多項式の係数列を持つ方法と比べて、累積和への移行が簡単になります）。

• \(R_i\)
• \(f_i(1), f_i(2), \ldots, f_i(N+2-i)\)
• \(F_i(0), F_i(1), \ldots, F_i(N+2-i)\)

\(R_i\) は、\(R_{N+1} = M\) および \(R_i = \left\lfloor \frac{R_{i+1}}{A_i}\right\rfloor\) により計算できます。\(F_i\) は \(F_i(x) = \sum_{1\leq y\leq x}f_i(y)\) により計算できます。

\(f_i\) は \(f_i(x) = F_{i+1}(R_{i+1}) - F_{i+1}(A_ix - 1)\) により計算できます。この際、直接保持していないところの \(F_{i+1}\) の値が必要になりますが、これは以下に述べる多項式補間により計算できます。

多項式補間

\(n\) 次多項式 \(F\) があり、\(F(0), \ldots, F(n)\) が既知であるとき、任意の \(x\) に対して、\(F(x)\) の計算が \(O(n)\) 時間で行えます。評価点が等間隔に並んでいることを用いると、Lagrange 補間を \(O(n)\) 時間で行えるためです。

参考：https://atcoder.jp/contests/arc033/tasks/arc033_4

---

◆計算量解析・計算量削減

以上をそのまま実装すると、計算量は \(i\) ごとに \(O(N^2)\) 時間。全体として \(O(N^3)\) 時間となります。

ところで、\(N\) が大きな場合、ほとんどの \(A_i\) は \(1\) に等しいです。\(A_i = 1\) の場合、多項式補間パートのほとんどは「\(F(0), \ldots, F(n)\) と \(0\leq x\leq n\) が与えられたとき、\(F(x)\) を計算せよ」という形の問題です。これは当然 \(O(1)\) 時間で計算できます（保持している値を読むだけです）。

このような「自明な多項式補間」を \(O(1)\) 時間で行うことで、本問題は全体として \(O(N^2\log M)\) 時間で解くことができます。\(A_i\geq 2\) となる \(i\) に対して \(O(N^2)\) 時間、\(A_i = 1\) となる \(i\) に対して \(O(N)\) 時間となるためです。

（高速な multipoint evaluation アルゴリズムを用いることで \(O(N\log^2N\log M + N^2)\) 時間で解くこともできます）