WC2014时空穿梭 反演
[WC2014]时空穿梭 如果推式子足够熟练的话，可以一路推出来的。但是我推着推着就迷惑了。。 首先要找的是直线。那么确定直线最好的办法是确定两个端点。考虑枚举两个点，坐标分别为$(a_1,a_2…),(b_1,b_2,…)$，那么必须有$\exists i, a_i < b_i$。确定两个点之后，这条线上一共有$gcd_{i=1}^n(b_i-a_i)+1$个点。 那么答案为： $$ans=\sum_{a,b} \binom{gcd(b_i-a_i)-1}{c-2}$$ 对这个式子进行优化。首先我们只关心坐标差，枚举坐标差$\Delta_i = b_i-a_i$。 $$\sum_{1 \leq \Delta_i < m_i} \binom{gcd(\Delta_i )-1}{c - 2} \prod_{i \leq n} (m_i - \Delta_i) $$ 紧接着再枚举GCD为$g$ $$\sum_{g < min_m} \binom{g-1}{c-2} \sum_{ 1 \leq \Delta_i < m_i,gcd(\Delta_i) = g}\prod_{i \leq n} (m_i - \Delta_i)$$ 令后面这一坨为$f(g)$。为了去掉GCD的限制，考虑反演 $$f’(g) = \sum_{g d} f(d) = \sum_{ 1 \leq \Delta_i < m_i, g gcd(\Delta_i) }\prod_{i \leq n} (m_i - \Delta_i)$$ 那么GCD就可以去掉了。 $$\sum_{1 \leq \Delta_i < \lfloor \frac{m_i}{g} \rfloor} \prod(m_i - \Delta_ig)$$ 实际上考虑分配律这个式子可以把两个符号换一下位置。交换后后面是$\sum$，可以用等差数列求和公式。化简之后如下： $$f’(g)=\prod_{i \leq n} (\lfloor \frac{m_i - 1}{g} \rfloor m_i - \frac{d\lfloor \frac{m_i - 1}{g} \rfloor(1+\lfloor \frac{m_i - 1}{g} \rfloor)}{2}) $$ 反演的式子套进去，直接带入答案： $$ans=\sum_{g < min_m} \binom{g-1}{c-2} \sum_{g d} \mu(\frac{d}{g}) \prod_{i \leq n} (\lfloor \frac{m_i - 1}{d} \rfloor m_i - \frac{d\lfloor \frac{m_i - 1}{d} \rfloor(1+\lfloor \frac{m_i - 1}{d} \rfloor)}{2})$$ 有个取整，考虑取整的可能值是$O(n \sqrt m)$的。枚举所有可能的$\lfloor \frac{m_i - 1}{d} \rfloor$，看作常数，后面是一个$n$次多项式。暴力拆开 $$\sum_{0 \leq i \leq n} v_i \sum_{?\leq d \leq ?}d^i \sum_{g d} \mu(\frac{d}{g}) \binom{g-1}{c-2} $$ 对于这两个$?$，它们取决于取整的$d$的范围。那么后面这一堆$\sum$只取决于$c,?,i$，预处理出来就好了。 复杂度：$O(cmlogm+cmn+T\sqrt m n^3)$
1 | #include <bits/stdc++.h> |