题解 | #G

The Set of Squares

https://ac.nowcoder.com/acm/contest/81597/G

首先可以把每一个数扔掉完全平方因数(记录一下价值)后的数的质因数分解分为“小质数”和“大质数”,以 为边界,把“小质数”抽象成一个二进制数。

我们考虑 DP(你可以把它叫 01 背包,但物品重量是按照异或来相加的)。

先处理没有大质数因数的数,之后对于每一个大质数,进行处理,每一个大质数可以被抽象为分组背包,每一组中要去恰好偶数个物品。

具体贡献计算你可以自己思考或者看代码,记得要随时取模。

强推我的洛谷博客(或者说文章区)

如果渲染格式有问题,去我的洛谷博客

全部评论

相关推荐

05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务