ARC126F

[ARC126F] Affine Sort

給定一個長為 \(N\) 的序列 \(x\) ，定義 \(f(K)\) 表示滿足下述條件的 \((a,b,c)\) 個數：

• \(1\le c\le K,0\le a,b<c\) ；
• \((ax_i+b)\bmod c\) 遞增

可以證明 \(\lim \limits_{k\to \infty} \frac{f(K)}{k^3}\) 趨向一個定值，對 998244353 取模。

\(2\le N\le 10^3,\sum\limits_{i=1}^{N}X_i\le 5\cdot 10^5\) ， \(X_i\) 兩兩不同。

Solution

我們記 \(g(k)\) 表示 \(c=k\) 的滿足條件的 \((a,b)\) 對數，則：

引理1： \(\lim\limits_{k\to \infty} \frac{g(k)}{k^2}\) 趨向一個定值 \(C\) 。

是以 \(\lim\limits_{k\to \infty}\frac{f(K)}{K^3}=\lim\limits_{K\to \infty} \sum\limits_{k=1}^{K} \frac{g(k)}{K^3}=\lim\limits_{k\to \infty}\sum\limits_{k=1}^{K}\frac{Ck^2}{K^3}=\frac{C}{3}\) 。

約定 \(\{x\}\) 表示 \(x\) 的小數部分，例如 \(\{-5.2\}=0.8\) 。于是我們将原條件轉換為：\(\{\frac{ax_i+b}{c}\}\) 單調遞增。

因為 \(k\to \infty\) ，不難聯想到定義點集 \(D\subset \mathcal R^2\) ：\(D=\{(a,b)\in [0,1]^2 | \{ax_i+b\} 單調遞增 \}\) 。那麼，\(g(k)\) 可以看做是滿足 \(0\le a,b<k,(\frac{a}{k},\frac{b}{k}) \in D\) 的點的面積，即 \(g(k)=\text{area}(D)\)。

将這些 \(\{ax_i\}\) 都畫在一個機關圓上，它們需要逆時針排布。不難發現，這個 \(\{ax_i+b\}\) 單調遞增的充要條件是：\(\sum\limits_{i=1}^{n}\{a(x_{i+1}-x_i)\}=1\) 。同時若 \(a\) 合法，滿足條件的 \(b\) 個數為 \(\{a(x_1-x_n)\}\) 。