BZOJ 2614 梦的困境 题解

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2614

首先我们注意到,对于两个数ij,如果gcd(i,k)=gcd(j,k),那么ij是等价的。所以我们先预处理出所有k的约数(经打表发现不超过200个约数),然后将所有给出的数igcd(i,k)分类。

定义val[i][j]=i个箱子里满足gcd(num,k)=jnum个数(num是输入的那些数)。

再定义f[i][j]=i个箱子中按照题目要求选数,使得选择出来的数的乘积mul满足gcd(mul,k)=j的方案数。

怎么得到这个数组呢?

考虑只选择一个数的情况,那么f[i][j]=val[i][j]

以下所说的uv均为分类过后的uv(即与kgcduv

再考虑选择两个数的情况,假如我们选择的两个数是uv\ (u,v|k),那么f[i][gcd(u*v,k)]+=val[i][u]*val[i][v]

最后再定义dp[i][j]=i个箱子中,按照题目要求选数,使得选择出来的数的乘积mul满足gcd(mul,k)=j的方案数

怎么得到这个数组呢?

假如前i个箱子中,选择的数的乘积是u,在第i+1个箱子中选择出的数的乘积是v\ (u,v|k),那么有dp[i+1][gcd(u*v,k)]+=dp[i][u]*f[i+1][v]

具体实现上,我们需要将约数离散化以减少空间复杂度

 

发表评论

电子邮件地址不会被公开。

*