[CF][补题][递推计数][DP] codeforces 1043F Make It One

其实我用了一种操蛋的贪心试了一下,所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了,也没有办法再继续证明正确性,所以还是放弃了去看tutorial,发现果然没思路就是dp。。。

然后这又不是一个正常的dp,甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实,涉及到集合就很难操作。但是可以发现,如果这个集合存在,他的size是很小的,这里可以作为一个突破点去想。如果考虑枚举集合的大小,是否能有简单的计算方法。现在需要求的东西可以转化为,是否存在至少一个集合使得他的size为i然后gcd为1,当然这个也不好直接算,但如果再加一维,再枚举gcd,看看会不会有进展:这时候要求的转化为,是否存在至少一个集合,size为i,gcd为j。可以设一个dp[i][j]表示这种集合的数量,然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的,所有的选法有C(cntj,i)种,其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的,是因为他们的gcd=k*j,然后可以发现这些不符合要求的数量就是dp[i][k*j],这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了,这个边界也很有意思:因为只考虑k*j<=max(ai)的gcd,所以大于的就是0就可以了

继续阅读“[CF][补题][递推计数][DP] codeforces 1043F Make It One”

[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums

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

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

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

[母函数][容斥][FFT] UVa 12633 Super Rooks on Chessboard

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

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

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