【BZOJ】3434: [Wc2014]时空穿梭-莫比乌斯反演

传送门：bzoj3434

题解

枚举每一维的极差 $\\Delta x_i$ ，设 $d=gcd(\\Delta x_1,\\Delta x_2,...,\\Delta x_n)$ ，则这条直线上最多可以选出 $d$ 个整点(不包含起点)。

则

$ans=\\sum\\limits_{\\Delta x_1=1}^{m_1}\\dots\\sum\\limits_{\\Delta x_n=1}^{m_n}\\dbinom{d-1}{c-2}\\prod\\limits_{i=1}^n(m_i-\\Delta x_i)$

转成枚举 $d$

$\\sum\\limits_{d=1}^m\\dbinom{d-1}{c-2}\\sum\\limits_{\\Delta x_1=1}^{\\lfloor \\frac{m_1}{d}\\rfloor}\\dots\\sum\\limits_{\\Delta x_n=1}^{\\lfloor \\frac{m_n}{d}\\rfloor}[(\\Delta x_1,\\Delta x_2,...,\\Delta x_n)=1]\\prod\\limits_{i=1}^n(m_i-d\\Delta x_i)$

莫比乌斯反演一下

$\\sum\\limits_{d=1}^m\\dbinom{d-1}{c-2}\\sum\\limits_{k=1}^{\\lfloor\\frac md \\rfloor}\\mu (k)\\sum\\limits_{\\Delta x_1=1}^{\\lfloor \\frac{m_1}{dk}\\rfloor}\\dots\\sum\\limits_{\\Delta x_n=1}^{\\lfloor \\frac{m_n}{dk}\\rfloor}\\prod\\limits_{i=1}^n(m_i-dk\\Delta x_i)$

设 $T=dk$ ，得到

$\\sum\\limits_{T=1}^m(\\prod\\limits_{i=1}^n\\sum\\limits_{\\Delta x_i=1}^{\\lfloor \\frac {m_i}{T}\\rfloor}(m_i-T\\Delta x_i))\\sum\\limits_{d|T}\\binom{d-1}{c-2}\\mu(\\frac Td)$