Description
多测。
给定一个 \(n\) 维空间，需要在这 \(n\) 维空间内选取 \(c\) 个共线的点，要求：
- 这 \(c\) 个点每维坐标均单调递增，即第 \(i + 1\) 个点的第 \(j\) 维坐标必须严格大于第 \(i\) 个点的第 \(j\) 维坐标。
- 第 \(i\) 维坐标是整数且在 \([1, m_i]\) 中。
Solution
先考虑有多少条直线，一条直线可由 起点 和 终点与起点的差向量 确定。
确定差向量为 \((x_1, x_2, \cdots, x_n)\) 后起点的第 \(i\) 维坐标可以在 \([1, m_i - x_i]\) 中取，共 \(\prod_{i = 1}^n (m_i - x_i)\) 种，此时终点也随之确定。
令 \(d = \gcd(x_1, x_2, \cdots, x_n)\)，则这一条差向量上的整点，不算起点与终点共 \(d - 1\) 个（分别是 \(\left(\dfrac{x_1}{d}, \dfrac{x_2}{d}, \cdots, \dfrac{x_n}{d}\right)\) 的 \(1\sim d - 1\) 倍）。
那么除起点与终点，在其中选 \(c - 2\) 个共有 \(\dbinom{d - 1}{c - 2}\) 种方法。
所以答案就是
\[\sum_{x_1 = 1}^{m_1} \sum_{x_2 = 1}^{m_2}\cdots\sum_{x_n = 1}^{m_n} \dbinom{\gcd\{x_i\} - 1}{c - 2} \prod_{i = 1}^n (m_i - x_i) \]于是就可以愉快地进行反演了，设 \(m = \min\{m_i\}\)。
\[\begin{aligned} ans & = \sum_{d = 1}^m \dbinom{d - 1}{c - 2} \sum_{x_1 = 1}^{m_1} \sum_{x_2 = 1}^{m_2} \cdots \sum_{x_n = 1}^{m_n} [\gcd\{x_i\} = d] \prod_{i = 1}^n (m_i - x_i) \\ & = \sum_{d = 1}^m \dbinom{d - 1}{c - 2} \sum_{x_1 = 1}^{\left\lfloor\frac{m_1}{d}\right\rfloor} \sum_{x_2 = 1}^{\left\lfloor\frac{m_2}{d}\right\rfloor} \cdots \sum_{x_n = 1}^{\left\lfloor\frac{m_n}{d}\right\rfloor} [\gcd\{x_i\} = 1] \prod_{i = 1}^n (m_i - dx_i) \\ & = \sum_{d = 1}^m \dbinom{d - 1}{c - 2} \sum_{k = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \mu(k) \sum_{x_1 = 1}^{\left\lfloor\frac{m_1}{dk}\right\rfloor} \sum_{x_2 = 1}^{\left\lfloor\frac{m_2}{dk}\right\rfloor} \cdots \sum_{x_n = 1}^{\left\lfloor\frac{m_n}{dk}\right\rfloor} \prod_{i = 1}^n (m_i - dk x_i) \\ & = \sum_{T = 1}^m \sum_{d\mid T} \dbinom{d - 1}{c - 2} \mu\left(\dfrac{T}{d}\right) \prod_{i = 1}^n \sum_{x_i = 1}^{\left\lfloor\frac{m_i}{T}\right\rfloor} (m_i - T x_i) \\ & = \sum_{T = 1}^m \sum_{d\mid T} \dbinom{d - 1}{c - 2} \mu\left(\dfrac{T}{d}\right) \prod_{i = 1}^n \left\lfloor\dfrac{m_i}{T}\right\rfloor m_i - T\dfrac{\left\lfloor\frac{m_i}{T}\right\rfloor(\left\lfloor\frac{m_i}{T}\right\rfloor + 1)}{2} \\ \end{aligned} \]此时可以做到 \(\Omicron(Tnm)\)。
首先 \(\left\lfloor\dfrac{m_i}{T}\right\rfloor\) 可以整除分块，然后退回到上一步
\[ans = \sum_{T = 1}^m \sum_{d\mid T} \dbinom{d - 1}{c - 2} \mu\left(\dfrac{T}{d}\right) \prod_{i = 1}^n \sum_{x_i = 1}^{\left\lfloor\frac{m_i}{T}\right\rfloor} (m_i - T x_i) \]其中
\[\prod_{i = 1}^n \sum_{x_i = 1}^{\left\lfloor\frac{m_i}{T}\right\rfloor} (m_i - T x_i) \]是关于 \(T\) 的 \(n\) 次多项式，设系数为 \(f_i\)。
再设
\[g(n) = \sum_{d\mid n} \dbinom{d - 1}{c - 2} \mu\left(\dfrac{n}{d}\right) \]那么在整除分块中
\[\sum_{T = l}^r g(T) \sum_{i = 0}^n f_i T^i = \sum_{i = 0}^n f_i \sum_{T = l}^r g(T) T^i \]于是我们需要预处理 \(g(n) n^i\) 的前缀和，设其为 \(S(n, c, i)\)，这一步是 \(\Omicron(cnm)\) 的。
由于有 \(n\) 个 \(m_i\)，所以整除分块*有 \(\Omicron(n\sqrt m)\) 个块，再加上每个块需要 \(\Omicron(n)\) 求和，所以这一段是 \(\Omicron(Tn^2\sqrt m)\) 的。