记公式：
Or operation:
arr[k + step] += opt * arr[k]
And operation:
arr[k] += opt * arr[k + step]
Xor operation:
A = arr[k], B = arr[k + step]
arr[k] = A + B, arr[k + step] = A - B
with inverse-operation, the inv2 is needed:
arr[k] /= 2, arr[k + step] /= 2;
这算是广义后缀自动机的一个通用(general)运用。我们可以像统计多个串一样来做这个，只不过我们需要在树上 DFS 时记录分岔点的 SAM 节点，然后进行回溯。剩下计算本质不同字串个数的方法就很套路了。
先写出答案的式子：
\[ \prod_{i = 1}^n \prod_{i = 1}^m f(\gcd(i, j)) \]
老套路，枚举公约数：
\[ \prod_{d = 1}^{\min(n, m)} f(d)^{\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = d]} \]
首先来一波正常套路，把枚举项变成\(\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\)个球选位置。