分类： ACM题解

题意：给出一个多项式，判断它是不是在所有整数点都取值为整数。

一个屌丝做法就是可以每次都随机数，只要数量足够一定可以把非整数判断出来。正解是利用数组差分的操作和取模的性质，自己想真的想不到。。

其实如果考虑思考方向的话，对于数据，一开始的思路应该是，既然有100个阶那肯定不是用某种解析的方式去做，而是选择一些点代入判定。这样的话问题变成了代入哪些点。首先如果分母上的数字比较小，那么可以算0-D之间的所有数字，但是D也很大，就没办法这么算了。这时候可以发现唯一可操作的只有阶的数量，然后就应该往这个方面去想了。。。当然这个数学归纳法的差分确实是有难度的，很难想到。。
沈阳赛得来的教训：模拟一定要在纸上写好所有情况再敲代码。。。

继续阅读“[数学][差分数列][数学归纳法][模拟] LA4119 Always an integer”

https://cn.vjudge.net/problem/SPOJ-TSUM

跟焦作选拔的时候那个题目的思路完全一样，用母函数可以考虑到所有的情况，然后去掉三个重复的和两个重复的再除以6就得到了去重后的结果。

收获主要是发现了FFT那个乘法的操作可以全部在一次循环里完成。。。神奇。。还有就是移位操作可以避免复数，而输出的时候记着要移回去原位。 继续阅读“[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums”

一开始看了很久不知道怎么求被对角线覆盖到而没有被横纵覆盖到的格子数，后来忽然发现可以把没被占用的横纵坐标标记为1啊！这样两个卷积起来就是没有被横纵占用的对角线上的格子数量了！！！然后遍历每条对角线，如果被覆盖到了就减去这上面没有被横纵覆盖到的格子！

wa点：日常LL，以及他这个操蛋的横纵坐标标识法，有点难受，得把棋盘左右反转一下才好做。

继续阅读“[母函数][容斥][FFT] UVa 12633 Super Rooks on Chessboard”

评论区大佬：嗯这个题贪心很明显啦然后nlogn方法也有很多种

http://codeforces.com/contest/980/problem/E

要使得去掉一些点之后剩下的仍然是一棵树，那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点？可以发现，如果i<j，那么去掉j一定不如去掉小于j的所有数，因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1，所以贪心策略就是能不去掉大的就不去，所以要从n-1开始一个一个找（由于k<n所以节点n一定不会被去掉），怎么确定一个点是否能被保留下来，只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求（想一下，如果这个点离最近的保留点太远了，远到了如果保留这个就没法保证能去掉k个点了，那就肯定不能留了），要保留这个点一定也要保留从这个点往上回溯所有的点，然后就会发现在以root为根的树上，这个01标志是连续的分布的，也就是说有一段1111然后一段000，这样的话就可以二分求分界点，而树上的二分就是lca里的倍增算法了，用倍增法查找就可以在logn时间内找到分界点，找到之后判断是否满足要求，如果满足则把分界点到当前点都标记上保留（话说这样logn不就退化了吗。。。）

wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。

继续阅读“[树上倍增][贪心][数据性质] codeforces 980E The Number Games”

http://codeforces.com/contest/1064/problem/E

又是喜闻乐见的交互+二分，这个已经在cf的讨论区被吐槽两次了，每次出交互题都是二分。。。我一开始没有搞懂题意，以为是你随便给他出点它会自动调整让点可以分为两片区域，后来才意识到他是给定了点的颜色分布，就是第几个点你只要问就是安排好的，也就是说这个需要你掌握问的点的坐标。。。

但是在不知道下一个点是什么的时候如何发问呢，首先想简化的过程，如果问的点全在一条线上会发生什么：假设左边为白点右边为黑，那么那个分界线一定是先往一个方向走了几步，然后又得回头往另一个方向走，如此反复。那么如何保证每次“回头”都可以有足够的余地让继续走下去而不与之前定好的界限相交？想到了一个叫二分的东西。。在倍增法的实现里其实就可以发现，他每次都会减半所以每次都不会覆盖到原来的部分。

但是这个题目直接二分又是有问题的，因为最多可以有30个点，而[log2(1e9)]==29，也就是说有一种情况可能最后会有俩点重合，为了避免这种情况可以先ask一个(0,0)，并且以此确定左半边的颜色，而不是像一开始说的一样自己定左右颜色。这样的话就剩下了29个点需要处理了，1e9的范围可以保证无论如何二分都可以达到没有任何两个点重合的结果。这样的话只需要在分界处的两个点之间画一条斜线就可以了。

因为这个29的坑wa了n发。。。

继续阅读“[二分][精度][思维] codeforces1064E Dwarves, Hats and Extrasensory Abilities”

思路简单，就是求出来结果的所有质因数的指数+1乘起来就行了。

首先由于题目的要求这里读入的ai只有两种情况，要么ai=p*q是两个不相等素数的乘积，要么ai=p^k，其中k取2，3，4。显然后一种情况很容易处理，但是第一种就有些难受了，直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法（这个看tutorial的评论区神仙各有千秋）。但是由于第一类的数只能分解成两个质因数，而且我们最后要的是质因数的指数而不需要关心质因数本身是多少，所以就有了更好的策略：如果一个数字的质因数在其他数字中出现过，那么一定可以通过gcd求出来，这时候等于说另一个质因数直接一除也能求出来，等于这个ai就完全解决了，像第二种情况一样加到map里即可；如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了，但是我们可以知道出现了俩独特的质因数，他出现且仅出现在所有aj==ai里，那么我们可以把ai直接存进map里，存起来他对应的加了多少次，另外要单独开一个set记录下来哪些ai是这样的ai，最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。

所以说一定要分析所给数据的性质，他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*，而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的，这个小的不超过1e5好像，所以那个是只需要枚举小的然后判断大的是否为质数即可。

继续阅读“[数学][大整数质因数分解] codeforces1033D Divisors”