在一个 \(n\) 维空间中，求一个点可以用一个 \(n\) 维向量 \((x_1,x_2,\dots x_n)\) 表示。现在要选出 \(c\) 个点，有三个限制：
设 \(x_i\) 表示任意一个点的第 \(i\) 个分量，那么 \(x_i\in [1,m_i],x_i\in Z\) 。选出的所有点在同一条直线上。问方案数。 \(T\le 100,n\le 11,c\le 20,m_i\le 10^5\) 。
好题！！！
看到这种感觉比较难入手的统计方案数问题，我们可以先尝试枚举一些东西，把问题变简单再计算。如果是很复杂的问题（比如说这里的 \(n\) 维），可以先从简单的情况开始推理。这里我们从 \(n=2\) 开始想，第一步枚举这条线的两端，或者枚举每个分量上的长度再枚举起点：\[ \sum _{x=1}^{m_1}\sum _{y=1}^{m_2}\sum _{i=1}^{m_1-x}\sum _{j=1}^{m_2-y}\binom {gcd(x,y)-1}{c-2} \] 即枚举每个分量上的长度，那么这个线段上的整点个数就是 \(gcd(x,y)-1\) ，分别为 \((\frac{x}{gcd(x,y)},\frac{y}{gcd(x,y)}),(\frac{2x}{gcd(x,y)},\frac{2y}{gcd(x,y)}),\dots ,(\frac{(gcd(x,y)-1)x}{gcd(x,y)},\frac{(gcd(x,y)-1)y}{gcd(x,y)})\) ，统计取出 \(c-2\) 个的方案数（ \((0,0)\) 和 \((x,y)\) 已经取了）。用经典的莫比乌斯函数方法对这个式子实施一些变形。设 \(m_1\le m_i\) ：\[ \begin{aligned} ans&=\sum _{d=1}^{m_1}\binom {d-1}{c-2} \sum _{x=1}^{\lfloor\frac{m_1}{d}\rfloor}\sum _{y=1}^{\lfloor\frac{m_2}{d}\rfloor}[gcd(x,y)=1](m_1-dx)(m_2-dy) \\ &=\sum _{d=1}^{m_1}\binom {d-1}{c-2} \sum _{x=1}^{\lfloor\frac{m_1}{d}\rfloor}\sum _{y=1}^{\lfloor\frac{m_2}{d}\rfloor}(m_1-dx)(m_2-dy)\sum _{e|x,e|y}\mu (e) \\\ &=\sum _{d=1}^{m_1}\binom {d-1}{c-2}\sum _{e=1}^{\lfloor\frac{m_1}{d}\rfloor}\mu (e)\sum _{x=1}^{\lfloor\frac{m_1}{de}\rfloor}\sum _{y=1}^{\lfloor\frac{m_2}{de}\rfloor} (m_1-xde)(m_2-yde) \end{aligned} \] 令 \(f(m,k)=\sum _{i=1}^{\lfloor\frac{m}{k}\rfloor}(m-ik)\) ，那么就有\[ \begin{aligned} ans&=\sum _{d=1}^{m_1}\binom {d-1}{c-2}\sum _{e=1}^{\lfloor\frac{m_1}{d}\rfloor}\mu (e)\prod _{i=1}^nf(m_i,de) \\ &=\sum _{a=1}^{m_1}(\prod _{i=1}^nf(m_i,a))\sum _{d|a}\mu (\frac{a}{d})\binom {d-1}{c-2} \end{aligned} \] 注意，这里我们已经把结论推广到 \(n\) 维的情况了——找到每一维独立的东西，按同样的方式加入。再看看 \(f\) 的形式：\[ \begin{aligned} f(m,k)&=\sum _{i=1}^{\lfloor\frac{m}{k}\rfloor}(m-ik) \\ &=m\lfloor\frac{m}{k}\rfloor-k\frac{\lfloor\frac{m}{k}\rfloor(\lfloor\frac{m}{k}\rfloor+1)}{2} \end{aligned} \] 这里面带有 \(k\) 的底式很难处理。而注意到数据范围比较小，我们可以直接对于一种 \(\lfloor\frac{m}{k}\rfloor\) 把 \(f(m,k)\) 多项式直接乘出来。设得到的多项式系数向量为 \(b\) ，那么：\[ \begin{aligned} ans&=\sum _{a=down}^{up}\sum _{j=0}^nb_ja^j\sum _{d|a}\mu (\frac{a}{d})\binom {d-1}{c-2} \end{aligned} \] 如果我们预先处理出 \(g(a,c,k)=a^k\sum _{d|a}\mu (\frac{a}{d})\binom {d-1}{c-2}\) 的前缀和，那么我们就可以分段快速计算答案了。
接下来分析复杂度。预处理的复杂度为 \(O(mc\ln m+nmc)\) ，前一个为枚举倍数的调和级数计算 \(g(a,c,0)\) ，后面的是递推得到 \(g(a,c,k)\) 的前缀和。
整个查询会被分成最多 \(2n\sqrt m\) 段，每段中需要暴力乘出多项式，这个复杂度为 \(n^2\) ，所以总复杂度为 \(O(mc\ln m+nmc+n^3\sqrt m)\) 。可能我的常数比较大，所以bzoj上过不了。uoj总用时4秒。
有一个需要注意的地方，由于这题的模数是 \(10^4+7<m\) ，我们求组合数就不能用阶乘来求，由于这题的数据范围比较小，可以直接递推出所有的。在线性筛 \(\mu\) 函数的时候记得对 \(\mu\) 取模。
转载于:https://www.cnblogs.com/owenyu/p/7351530.html
相关资源：25个经典网站源代码