题解：P4152 [WC2014] 时空穿梭

· · 题解

我们考虑枚举每一条直线，一条线可以用两个点来表示。假设我们定一个向量 \vec{x}=(x_1,x_2,x_3……,x_n) ，那么第一个点可以取 \prod_{i=1}^n(m_i-x_i) 种，令 d=\gcd(x_1,x_2……) ，那么这条线上只有 d 个整点。可以得式子：

\sum_{t_1=1}^{m_1}\sum_{t_2=1}^{m_2}……\sum_{t_n}^{m_n}\binom{d-1}{c-2}\prod_{i=1}^n(m_i-t_i)

然后就是推了。

\sum_{t_1=1}^{m_1}\sum_{t_2=1}^{m_2}……\sum_{t_n}^{m_n}\binom{d-1}{c-2}\prod_{i=1}^n(m_i-t_i)\\ =\sum_{d=1}^{\min(m_1,m_2……)}\sum_{t_1=1}^{m_1}\sum_{t_2=1}^{m_2}……\sum_{t_n}^{m_n}\binom{d-1}{c-2}[\gcd(t_1,t_2……)=d]\prod_{i=1}^n(m_i-t_i)\\ =\sum_{d=1}^{\min(m_1,m_2……)}\binom{d-1}{c-2}\sum_{t_1=1}^{m_1}\sum_{t_2=1}^{m_2}……\sum_{t_n}^{m_n}[\gcd(t_1,t_2……)=d]\prod_{i=1}^n(m_i-t_i)\\ =\sum_{d=1}^{\min(m_1,m_2……)}\binom{d-1}{c-2}\sum_{t_1=1}^{\lfloor \frac{m_1}{d} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{d} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{d} \rfloor}[\gcd(t_1,t_2……)=1]\prod_{i=1}^n(m_i-dt_i)\\

莫反得 [\gcd(t_1,t_2……)=1]=\sum_{k|t_1,k|t_2……k|t_n}\mu(k) 。

=\sum_{d=1}^{\min(m_1,m_2……)}\binom{d-1}{c-2}\sum_{t_1=1}^{\lfloor \frac{m_1}{d} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{d} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{d} \rfloor}\sum_{k|t_1,k|t_2……k|t_n}\mu(k)\prod_{i=1}^n(m_i-dt_i)\\ =\sum_{d=1}^{\min(m_1,m_2……)}\binom{d-1}{c-2}\sum_{k=1}\mu(k)\sum_{t_1=1}^{\lfloor \frac{m_1}{dk} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{dk} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{dk} \rfloor}\prod_{i=1}^n(m_i-dkt_i)\\ =\sum_{T=1}\sum_{d|T}\binom{d-1}{c-2}\mu(\frac{T}{d})\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}\prod_{i=1}^n(m_i-Tt_i)

记 f(T,c)=\sum_{d|T}\binom{d-1}{c-2}\mu(\frac{T}{d}),g(n,T)=\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}\prod_{i=1}^n(m_i-Tt_i)

=\sum_{T=1}f(T,c)g(n,T) f(T,c)$ 是好算的，我们重点看 $g(n,T) g(n,T)=\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}\prod_{i=1}^n(m_i-Tt_i)\\ =\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}(m_1-Tt_1)(m_2-Tt_2)……(m_n-Tt_n)\\ =\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……(m_1-Tt_1)(m_2-Tt_2)……\sum_{t_n}^{\lfloor \frac{m_n}{T} \rfloor}(m_n-Tt_n)\\ $$ =\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……(m_1-Tt_1)(m_2-Tt_2)……(\lfloor \frac{m_n}{T} \rfloor m_i - \frac{T (\lfloor \frac{m_n}{T} \rfloor+1)\lfloor \frac{m_n}{T} \rfloor}{2})\\ =(\lfloor \frac{m_n}{T} \rfloor m_i - \frac{T(\lfloor \frac{m_n}{T} \rfloor+1)\lfloor \frac{m_n}{T} \rfloor}{2})\sum_{t_1=1}^{\lfloor \frac{m_1}{T} \rfloor}\sum_{t_2=1}^{\lfloor \frac{m_2}{T} \rfloor}……(m_1-Tt_1)(m_2-Tt_2)……\\ =(\lfloor \frac{m_n}{T} \rfloor m_i - \frac{T(\lfloor \frac{m_n}{T} \rfloor+1)\lfloor \frac{m_n}{T} \rfloor}{2})g(n-1,T)\\ =\prod_{i=1}^n(\lfloor \frac{m_n}{T} \rfloor m_i - \frac{(T\lfloor \frac{m_i}{T} \rfloor+1)\lfloor \frac{m_i}{T} \rfloor}{2}) $$ 这是不是可以看作一个 $T$ 的且系数只和 $\lfloor \frac{m_i}{T} \rfloor, m_i$ 有关的多项式，令 $xh_i$ 代表多项式的系数。 $$ =\sum_{i=0}xh_iT^i $$ 带回原式。 $$ =\sum_{T=1}f(T,c)\sum_{i=0}xh_iT^i\\ =\sum_{i=0}xh_i\sum_{T=1}f(T,c)T_i $$ 因为系数只和 $\lfloor \frac{m_i}{T} \rfloor, m_i$ 有关，所以一个整除分块来对系数预处理即可。 完结撒花\o/