今天上午还是一套题, 并且仍然不知道是谁出的......
题目的下载链接:task0116.pdf
题看起来都比较简单, 但是可能不是那么好写. 第一题明显是矩阵乘法加快速幂, 然后 我看了一眼发现构造也比较简单, 除了平常的高位还需要加上一个常数项, 于是简单构造 一发就可以搞定这道题了. 所以我就觉得没有写这题的必要, 然后就安安静静地去看下面地题目了.
看了一眼第二题, 发现有这样一些数论上的性质:
- \(x\) 的约数的个数是质数意味着它本身最多只有一个质因子, 令 \(x\)=\(p^n\), 则一定有 \(n+1\) 为质数.
- 令 \(x = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdot \ldots \cdot p_n^{a_n}\), 则 \(x\) 的所有约数的和为 \[\prod_{i=1}^{n} \prod_{j=0}^{a_i} p_i^j\] 那么 \(x\) 的所有约数的和是质数意味着 \(n=1\) 且 \(\prod_{j=1}^{a_1} p_1^j\) 为质数.
- 令 \(x = p_1^{a_1} \cdot p_2^{a_2} \cdot p_3^{a_3} \cdot \ldots \cdot p_n^{a_n}\), 则 \(x\) 的所有约数的乘积为完全平方数意味着 \(n \equiv 1 \bmod 2\) 时满足 \(\sqrt{x}\) 为完全平方数. 若 \(n \equiv 1 \bmod 4\) 则一定为完全平方数.
我们统计完这些性质以后就可以对这一堆数预处理了.
结果发现交上去 WA, 才发现重点在后面的 DP 上 (不然就太简单了). 后面大概是枚举以下总共的 16 种情况, 然后分类讨论 \(2^{16}\) 个选法等等, 所以其实时间复杂度是 \(O(1)\) 的 (雾).
第三道题似乎有一点贪心的想法, 但是没去想, 所以不管了.
但是其实有这样一种做法:
既然我们发现答案不会超过 \(50\), 而且本次测试清橙可以看到提交结果, 我们就可以先暴力求得所有 \(50\) 次的结果, 然后再用五分法下到数据的哈希值, 然后就可以通过此方法得到 AC 的代码.
这做法也是没谁了~
下午是罗剑桥老师讲课, 讲的是图论.
图论比较有意思, 毕竟把所有概念从头讲到尾, 但是概念感觉比例题要简单很多 (例题的难度太高 233333333). 然后这一天的题没有讲完 (似乎还有一些陈题), 留到后面去讲.
罗老师的演示文稿的下载链接:图论.pptx
求大神帮续实力啊...... orz