Official

Ex - Dice Product 2 Editorial by en_translator

Dynamic Programming

First, let’s consider the recurrence relation of DP (Dynamic Programming) to solve this problem.
A naive transformation of the problem statement to DP relations requires an \(\mathrm{O}(NM)\) time and an \(\mathrm{O}(M)\) complexity, which is of course too slow. In this case, let’s defined the following function:

  • \(f(x) :=\) the expected value of number of times of rolling the die, when “the current value multiplied by \(x\)” does not exceed \(M\).

Then, we obtain the following equation:

\[ \begin{aligned} &f(0) = 0 \\ &f(x) = 1 + \frac{1}{N} \sum_{i=1}^N f(\lfloor x/i \rfloor) \\ \iff &f(x) = \frac{N}{N-1} \left(1 + \frac{1}{N}\sum_{i=2}^N f(\lfloor x/i \rfloor)\right), \end{aligned} \]

and the answer is \(f(M)\).
By using the relation above, we can find the answer by memorized recursion, but what is the complexity of this algorithm (if computed properly)?

In order to prove it, we will enumerate some observations.

Observation 1

Let \(d\) be a positive integer. There are \(\mathrm{O}(\sqrt{M})\) number of possible values of \(\lfloor M / d\rfloor\).

This fact already appeared in ABC230-E, so we will omit the details. Let \(L = \lfloor \sqrt{M} \rfloor\) and \(K = \lfloor M/(L+1) \rfloor\) and consider \(x\) such that there exists a positive integer \(d\) such that \(x = \lfloor M/d \rfloor\). Then there are only two kinds of possible \(x\):

  • \(x=1,2,\dots,L\)
  • \(x=\lfloor M/1\rfloor,\lfloor M/2\rfloor, \dots,\lfloor M/K\rfloor\)

By this fact, we can use the technique of calculating for each quotient, just as in ABC230-E. Specifically, let

  • \(Q(x)\): (the set of positive integer \(q\) less than or equal to \(n\) such that there exists a positive integer \(d\) such that \(q = \lfloor x / d\rfloor\))
  • \(g(x, q)\): (The probability that \(\lfloor x/d\rfloor = q\) where \(d\) is the number shown by the die)

then we have

\[f(x) = \frac{N}{N-1} \left(1 + \sum_{q \in Q(x) \setminus \lbrace 1 \rbrace} g(x, q) f(q)\right),\]

so we can express \(f(x)\) as the sum of \(\mathrm{O}(\sqrt{x})\) number of \(f(q)\).

Observation 2

The following fact holds for positive integers \(i,j\), and \(M\):

\[\lfloor \lfloor M/i \rfloor / j \rfloor = \lfloor M / (ij) \rfloor\]

Here is a proof: \(M\) can be uniquely expressed as \(M = (qj + r)i + s\), where \(s\) and \(r\) satisfies \(0 \leq s \lt i, 0 \leq r \lt j\) and \(q\) is an integer. By assigning this to \(M\) in both hand sides, the equation can be proved. Of course, the fact can be similarly proved for three or more floor divisions, like \(f(\lfloor \lfloor \lfloor M / i \rfloor / j \rfloor / k \rfloor) = f(\lfloor M /(ijk) \rfloor)\).

Observation 3

In the algorithm of memorized recursion, \(f(x)\) has to be calculated only for \(x\) such that there exists a positive integer \(d\) such that \(\lfloor M / d \rfloor = x\).

This follows from Observation 2. In the recursion, \(f(M)\) calls \(f(\lfloor M / i \rfloor)\), which in turns calls \(f(\lfloor \lfloor M / i \rfloor / j \rfloor)\), …, but by Observation 1, all the arguments is equal to \(\lfloor M / d \rfloor\) (where \(d\) is the product of all divisors).

By Observations 1, 2, and 3, we can yield the following fact.

Observation 4

\(f(M)\) can be computed in an \(\mathrm{O}(M^{3/4})\) time.

By the observation above, we already know the following fact:

  • There are \(\mathrm{O}(\sqrt{M})\) number of values of \(f(x)\) required to compute \(f(M)\).
  • \(f(x)\) can be computed in a \(\mathrm{O}(\sqrt{x})\) number of computations.

By the fact above, it can be inferred that the complexity is at most \(\mathrm{O}(M)\); but in fact, it’s is even smaller.
As shown in Observation 1, the possible quotients \(x\) of \(M\) is a sum set of

  • \(x=1,2,\dots,L\) and
  • \(x=\lfloor M/1\rfloor,\lfloor M/2\rfloor, \dots,\lfloor M/L\rfloor\),

where \(L = \lfloor\sqrt{M}\rfloor\). The complexity of each part is:

  • The \(x=1,2,\dots,L\) part: \(\mathrm{O}(\sqrt{L}) \times L = \mathrm{O}(M^{3/4})\)
  • The \(x=\lfloor M/1\rfloor,\lfloor M/2\rfloor, \dots,\lfloor M/L\rfloor\) part: \(\mathrm{O}(\sum_{i=1}^L \sqrt{M/i}) = \mathrm{O}(\int_{t=1}^L \sqrt{M/t}) = \mathrm{O}(M^{3/4})\)

so each of them is proved to be \(\mathrm{O}(M^{3/4})\).

By the observations above, the problem above can be solved with an algorithm with an \(\mathrm{O}(M^{3/4})\) time and \(\mathrm{O}(M^{1/2})\) space complexity. With a proper implementation, it works fast enough, so it will be AC (Accepted).

A sample code in C++ follows.

#include <cmath>
#include <iostream>
using namespace std;
#include "atcoder/modint.hpp"
using mint = atcoder::modint1000000007;

mint low[50000], high[50000];

int main() {
  int N, M;
  cin >> N >> M;
  int L = llround(sqrt(M)), K = M / (L + 1);
  for (int i = 1; i <= L + K; i++) {
    int x = i <= L ? i : M / (L + K + 1 - i);
    mint sum = 0;
    for (int l = 2, r, le = min(N, x); l <= le; l = r) {
      int q = x / l;
      r = min(N, x / q) + 1;
      mint cur = q <= L ? low[q] : high[M / q];
      sum += cur * (r - l);
    }
    (i <= L ? low[i] : high[L + K + 1 - i]) = (sum + N) / (N - 1);
  }
  cout << (M <= L ? low[M] : high[1]).val() << "\n";
}
  • The values of \(f(x)\) can be stored in std::unordered_map, so that the implementation becomes easier.
#include <iostream>
#include <unordered_map>
using namespace std;
#include "atcoder/modint.hpp"
using mint = atcoder::modint1000000007;

mint solve(int N, int x) {
  static unordered_map<int, mint> memo;
  if (memo.count(x)) return memo[x];
  mint res = 0;
  for (int R = x, L, q; R; R = L) {
    q = x / R, L = x / (q + 1);
    if (q != x) res += solve(N, q) * (min(N, R) - min(N, L));
  }
  return memo[x] = (N + res) / (N - 1);
}

int main() {
  int N, M;
  cin >> N >> M;
  cout << solve(N, M).val() << "\n";
}

Advanced: prefix sum of multiplicative function

A function \(f(n)\) is said to be multiplicative if \(f(a)f(b) = f(ab)\) for all coprime positive integers \(a, b\).
Actually, this problem is based on the algorithm to compute the prefix sum of a multiplicative function, \(\sum_{i=1}^N f(i)\).
For more details, please refer to the following references.

With the technique introduced in the blogs above, the original problem can be solved in a total of \(\mathrm{\tilde{O}}(M^{2/3})\) time.

Also, the following problem can be solved with similar techniques.

posted:
last update: