[母函数][容斥][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”