首先来一波正常套路，把枚举项变成\(\gcd\)。
\[ \begin{aligned} \prod_{i = 1}^n \prod_{j = 1}^n \frac{lcm(i, j)}{gcd(i, j)} &= \prod_{i = 1}^n \prod_{j = 1}^n \frac{ij}{gcd(i, j)^2} \\ &= \prod_{d = 1}^n d^{\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d]} \end{aligned} \]
我们发现只需要保证在任何时候\(0\)的个数都大于等于颜色的数量。直接考虑一个一个塞球，不仅要考虑同质问题，还要考虑具体的颜色排列非常麻烦，不如我们一次性把所有的球都在序列上放好：设置\(dp[i][j]\)为\(i\)个\(0\)、\(j\)种颜色的局面，我们可以这样转移：
\[ dp[i][j] = dp[i – 1][j] + {n – i + (n – j + 1) \times (k – 2) – 1 \choose k – 2 } dp[i][j – 1] (n – j + 1) \]
解释一下：我们固定住该颜色的球的位置为最左能放置的点，然后乘上\(n – j + 1\)进行染色，并给剩余的\(k-2\)个球选位置。
也是比较巧妙的一个转换思想。
我们考虑列式：
\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]
直接去算或者是按贡献计算都不行，我们考虑转换成这样：
\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]
前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上，然后算一个路径计数的 DP 即可（因为平面大小比较小）。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数，后半部分直接暴力算即可。
好您妈神仙啊。
考虑用 Lucas 把组合数分解：
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上，配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串，且在后缀自动机上不会存在重复的子串信息（然而，我们可以进行一些扩展来维护子串位置信息）。