BZOJ 2614 梦的困境 题解

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

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

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

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

怎么得到这个数组呢?

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

以下所说的\(u\)和\(v\)均为分类过后的\(u\)和\(v\)(即与\(k\)的\(gcd\)为\(u\)和\(v\))

再考虑选择两个数的情况,假如我们选择的两个数是\(u\)和\(v\ (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]\)

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

 

发表评论

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

*