◆ Notation

• Let \(S = \sum_i |X_i|\) in analysis of complexity.
• For a positive integer \(K\), let \(g(K)\) denote the number of valid triples with \(c = K\), that is, pairs of integers \((a, b)\) that satisfy the following.
  • \(0\leq a, b < K\).
  • \(Y_1 < Y_2 < \cdots < Y_N\) holds, where \(Y_i\) is the remainder when \(aX_i+b\) is divided by \(K\) for each \(i\).

---

◆ Relation between \(f(K)\) and \(g(K)\)

We have \(f(K) = \sum_{k=1}^K g(k)\).

As explained later, it is possible to show that the limit \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\) exists. Let us assume this fact for now and find the answer.

Take an arbitrary positive real number \(\varepsilon > 0\). When \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\), \((c-\varepsilon)K^2 \leq g(K) \leq (c+\varepsilon)K^2\) holds for any sufficiently large \(K\). From this, \((c-2\varepsilon) \sum_{k=1}^Kk^2 \leq f(N) \leq (c+2\varepsilon)\sum_{k=1}^Kk^2 \) holds for any sufficiently large \(K\). Since \(\sum_{k=1}^K k^2 = \frac13K^3 + O(K^2)\), \((c-3\varepsilon)\cdot \frac13 K^3\leq f(K) \leq (c+3\varepsilon)\cdot \frac13 K^3\) holds for any sufficiently large \(K\).

This formula can be rephrase into \(\frac13 c - \varepsilon \leq \frac{f(K)}{K^3} \leq \frac13 c + \varepsilon\). From the fact that for any \(\varepsilon > 0\), there is a sufficiently large \(K\) that satisfies this inequation, we can see that \(\lim_{K\to\infty}\frac{f(K)}{K^3} = \frac13 c\).

Thus, under the assumption that the limit \(c = \lim_{K\to\infty} \frac{g(K)}{K^2}\) exists, it has been shown that the answer is \(\frac13 c\).

---

◆ Rephrasing with continuous values

Let us consider when \(Y_i = (aX_i + b)\bmod K\) are increasing. By considering \(Y_i / K\) instead of \(Y_i\), we can see that the decimal part of \(\frac{a}{K}X_i + \frac{b}{K}\) holds the key.

For a real number \(x\), let \(\{x\}\) denote its decimal part, that is, \(\{x\} = x - \lfloor x\rfloor\).

\(Y_i\) are increasing when \(\{(a/K)X_i + (b/K)\}\) are increasing, so let us define a subset \(D\) of \(\mathbb{R}^2\) as:

\(D = \{(\alpha, \beta) \in [0,1]^2\mid \{\alpha X_1 + \beta\} < \{\alpha X_2 + \beta\} < \cdots\}\).

\(g(K)\) can be seen as the number of pairs \(0\leq a,b <K\) such that \((a/K, b/K) \in D\). As explained below, \(D\) is a union of figures surrounded by a finite number of segments, and \(\lim_{K\to \infty} \frac{g(K)}{K^2}\) equals the area of \(D\).

The answer is the area of \(D\) multiplied by \(1/3\), so let us try to find this area.

---

◆ Computing \(D\)

Since pairs \((\alpha, \beta)\) such that \(\{\alpha X_i + \beta\} = \{\alpha X_{i+1} + \beta\}\) exactly holds are irrelevant to the area of \(D\), we ignore this case in the argument below.

Let us see the interval \([0, 1)\) as a circumference by pasting together the ends, \(0\) and \(1\), and consider \(\{\alpha X_i + \beta\}\) to be a point on this circumference. Then, \(\{\alpha X_i + \beta\}\) is the result of translating \(\{\alpha X_i\}\) by \(\beta\) in the positive direction. We can see that, when \(\{\alpha X_i + \beta\}\) are increasing, \(\{\alpha X_i\}\) are also in the order \(i=1, 2, \ldots\) when seen from some position on the circumference. Let us first examine the condition that \(\alpha\) must satisfy to make this happen.

---

\(\{\alpha X_i\}\) are in the order \(i=1, 2, \ldots\) when seen from some position on the circumference, if and only the following holds for any \(i\):

• \(\sum_{i=1}^N f_i(\alpha) = 1\) holds, where \(f_i(\alpha)\) is the distance from \(\{\alpha X_{i}\}\) to \(\{\alpha X_{i+1}\}\) measured in the positive direction. (Here, we define \(X_{N+1} = X_1\).)

When \(\alpha\) continuously increases from \(0\) to \(1\), \(f_i(\alpha) = \{\alpha(X_{i+1} - X_i)\}\) changes at the rate \(X_{i+1} - X_i\) around most points, and changes by \(\pm 1\) at a finite number of rational numbers whose denominator is \(|X_{i+1} - X_i|\).

\(\sum_i f_i(\alpha)\) is constant around most points and changes by an integer value at a finite number of border points. Thus, we can enumerate all ranges of \(\alpha\) where \(\{\alpha X_i\}\) are in desired relative positions on the circumference, by computations such as enumerating rational numbers whose denominators are \(|X_i - X_{i+1}|\) and sorting them. Since \(\sum |X_i - X_{i+1}| = O(S)\), this can be done in \(O(S\log S)\) time.

Furthermore, when \(\alpha\) satisfies this condition, the condition that \(\beta\) should satisfy can be represented as \(\{\alpha X_1 + \beta\} < \{\alpha X_N + \beta\}\). In the end, the area of \(D\) can be computed as the sum of \(\int_{l}^r \{\alpha (X_1 - X_N)\} d\alpha\) over a finite number of open intervals \((l,r)\).

---

◆ Proof that \(\frac{g(K)}{K^2}\) converges to the area of \(D\)

Let \(\mu(D)\) denote the Lebesgue measure of the set \(D\subset \R^2\). Also, let \(D^{\circ}\) and \(\overline{D}\) respectively denote the interior and closure of \(D\). Furthermore, let us define the indicator function \(\chi_D\) of the set \(D\) as \(\chi_D(x) = \begin{cases} 1 & (x\in D)\\0 & (x\notin D)\end{cases}\).

Let us show that the following holds.

Assume that \(D\subset \mathbb{R}^2\) is bounded and its boundary is a null set, that is, \(\mu(D^{\circ}) = \mu(\overline{D})\) holds. Let \(g(K)\) be the number of pairs \(a, b\in \mathbb{Z}\) such that \((a/K, b/K) \in D\). Then, \(\lim_{K\to\infty} \frac{g(K)}{K^2} = \mu(D)\) holds.

Let us define the sets of points \(A_K, A_K^{\circ}, \overline{A}_K\) as follows:

• \(A_K = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, (a,b) \in D\}\),
• \(A_K^{\circ} = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, [a,a+1/K) \times [b,b+1/K) \subset D^{\circ}\}\),
• \(\overline{A}_K = \{(a,b)\mid Ka\in \mathbb{Z}, Kb\in \mathbb{Z}, [a,a+1/K) \times [b,b+1/K) \cap \overline{D}\neq \emptyset\}\).

Also, let the functions \(F^{\circ}_K, \overline{F}_K\) defined as follows:

• \(F^{\circ}_K\) is the indicator function of \(\bigcup_{(a,b)\in A_K^{\circ}} [a,a+1/K)\times [b,b+1/K)\),
• \(\overline{F}_K\) is the indicator function of \(\bigcup_{(a,b)\in \overline{A}_K} [a,a+1/K)\times [b,b+1/K)\).

Then, we can see the following:

• \(A_K^{\circ}\subset A_K\subset \overline{A}_K\),
• \(\int_x F^{\circ}_K(x) dx = |A_K^{\circ}| / K^2\),
• \(\int_x \overline{F}_K(x) dx = |\overline{A}_K| / K^2\),
• \(\lim_{K\to\infty} F^{\circ}_K(x) = \chi_{D^{\circ}}(x)\) pointwise,
• \(\lim_{K\to\infty} \overline{F}_K(x) = \chi_{\overline{D}}(x)\) pointwise.

From the boundedness of \(D\), we can apply Lebesgue’s convergence theorem to see that \(\lim_{K\to\infty} \int_{\R^2}F^{\circ}_K(x)dx = \int_{\R^2}\chi_{D^{\circ}}(x)dx\). Thus, we have \(\lim_{K\to\infty} |A^{\circ}_K|/K^2 = \mu(D^{\circ})\). Similarly, \(\lim_{K\to\infty} |\overline{A}_K|/K^2 = \mu(\overline{D})\).

From \(A_K^{\circ}\subset A_K\subset \overline{A}_K\), \(\mu(D^{\circ}) = \mu(\overline{D})\), and the squeeze theorem, we can see that \(\lim_{K\to\infty} |A_K|/K^2 = \mu(D)\) holds, which completes the proof.

---

\(D\) in this problem is the union of regions defined by a finite number of linear inequalities, whose boundary is contained in the union of a finite number of lines. Thus, it satisfies the assumption above that its boundary is a null set.