◆Recurrence Formula

For positive integers \(n\) and \(x\), let \(\text{dp}_n(x)\) denote the number of sequences \(X = (X_n, \ldots, X_{N+1})\) starting at the \(n\)-th element, satisfying the conditions and \(X_n = x\). Then, the recurrence formula below determines \(\text{dp}_n(x)\) for \(n = N+1, N, \ldots, 1\), in this order.

• \(\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)\)

The answer is \(\sum_{x} \text{dp}_1(x)\), but \(M\) is too huge to compute \(\text{dp}_i(x)\) directly for each \(x\).

---

◆\(\text{dp}_i\) and Polynomials

For \(i = N+1, N, \ldots, 1\), we can recursively prove the existence of the following integers \(R_i\) and polynomials \(f_i, F_i\):

• \(\text{dp}_i(x) = 0\) if \(x > R_i\).
• \(f_i\) has a degree of \(N+1-i\) and satisfies \(\text{dp}_i(x) = f_i(x)\) for each \(1\leq x\leq R_i\).
• \(F_i\) has a degree of \(N+2-i\) and satisfies \(\sum_{1\leq y \leq x}\text{dp}_i(y) = F_i(x)\) for each \(0\leq x\leq R_i\).

Now, instead of maintaining a big table \(\text{dp}_i(x)\), let us maintain \(R_i, f_i, F_i\).

---

◆How to Maintain Polynomials and Compute Them

There are several ways to maintain data that is equivalent to a polynomial \(f_i\). Here, let us store the following values, which makes it easier to handle prefix sums than storing coefficients of the polynomial.

• \(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)\)

We can compute \(R_i\) from \(R_{N+1} = M\) and \(R_i = \left\lfloor \frac{R_{i+1}}{A_i}\right\rfloor\), and compute \(F_i\) from \(F_i(x) = \sum_{1\leq y\leq x}f_i(y)\).

\(f_i\) can be computed from \(f_i(x) = F_{i+1}(R_{i+1}) - F_{i+1}(A_ix - 1)\). Here we need the value of \(F_{i+1}\) at a point that is not directly stored, but we can compute it through polynomial interpolation described below.

Polynomial Interpolation

When we have a polynomial \(F\) of degree \(n\) and know the values \(F(0), \ldots, F(n)\), we can compute \(F(x)\) in \(O(n)\) time for any \(x\). This can be done by performing Lagrange interpolation in \(O(n)\) time using the fact that the evaluation points are evenly spaced.

Reference: https://atcoder.jp/contests/arc033/tasks/arc033_4

---

◆Analysis of Complexity and How to Reduce It

Straight forward implementation of the above results in \(O(N^2)\) time for each \(i\), for a total of \(O(N^3)\) time.

Here, note that almost all \(A_i\) is \(1\) when \(N\) is large. If \(A_i\) is large, almost all of the things we have to do in polynomial interpolation is to compute \(F(x)\) when \(F(0), \ldots, F(n)\) and \(0\leq x\leq n\) are given. We can obviously compute it in \(O(1)\) time by just reading the value stored.

By performing this “obvious” polynomial interpolation in \(O(1)\) time, we can solve the problem in a total of \(O(N^2\log M)\) time: \(O(N^2)\) time for each \(i\) where \(A_i\geq 2\), and \(O(N)\) time for each \(i\) where \(A_i = 1\).

We can also use a fast multipoint evaluation algorithm to solve the problem in \(O(N\log^2N\log M + N^2)\) time.