BZOJ4652 [NOI2016]循环之美

发布于 2018-01-21  3.82k 次阅读


题目链接(UOJ)

反演+杜教筛神题,大概可以推到多数人解法的84分那里,剩下的部分会一种记忆化的方法(复杂度玄学,但是跑的比他们快)。

首先,不管是打表还是瞎猜得到题目要求的式子,之后化简成这个样子:

$$\sum_{i=1}^{n} \sum _{j=1}^{m} [gcd(i,j)=1]\, [gcd(j,k)=1] \\
=\sum_{j=1}^m\, [gcd(j,k)=1]\: \sum_{i=1}^{n}[gcd(i,j)=1] \\
=\sum _{j=1}^{m}\sum_{d|j,d|k}\mu(d)\sum_{i=1}^{n}[gcd(i,j)=1]\\
=\sum_{d=1}^{n} \mu(d) \sum _{t=1} ^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{i=1}^{n}[gcd(i,dt)=1]\\
=\sum_{d=1}^{n} \mu(d) \sum _{t=1} ^{\left \lfloor \frac{m}{d} \right \rfloor} \sum_{i=1}^{n}[gcd(i,t)=1][gcd(i,d)=1]$$

而mu后面的式子就是我们问题的子问题,设F(n,m,k)为所求函数,那么带进去,就有如下关系成立:

$$F(n,m,k)\\
=\sum _{i=1}^{n} \sum_{j=1}^{m}[gcd(i,j)==1]+\sum_{d|k,d>1}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[gcd(i,dj)=1]\\
=\sum _{i=1}^{n} \sum_{j=1}^{m}[gcd(i,j)==1]+\sum_{d|k,d>1}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[gcd(i,j)=1][gcd(i,d)=1]\\
=\sum _{i=1}^{n} \sum_{j=1}^{m}[gcd(i,j)==1]+\sum_{d|k,d>1}\mu(d)F(m/d,n,d)$$

因为k<=2000,所以后面那个式子可以暴力计算,对于每个k可以预处理出可行的d作为减枝,用哈希表实现记忆化,用杜教筛实现mu的前缀和,然后就可过了。

另外,对于这种题目,要求用哈希表实现记忆化的,一定要使用双取模,否则很难通过所有数据。然后为了卡常,我又把用来保存hash的long long换成了int,BZOJ上快了3秒。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974