【BZOJ 4115】[WF2015] Tile Cutting

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4115
神犇题解:http://www.cnblogs.com/clrs97/p/4779789.html
英文题面:https://online.acmicpc.org/problems/tiles
英文题解:http://blog.brucemerry.org.za/2015/05/analysis-of-icpc-2015-world-finals.html

解题报告

卧槽,这样乱找题做吃枣药丸啊!
一言不合就FFT+生成函数,FFT还好,生成函数完全不会啊 QwQ
只能先弃坑了,以后慢慢来填 _ (:з」∠) _

—– UPD 2017.1.22 —–
最近听集训队神犇讲了生成函数
然而并没有学会 QwQ
不过做这个题还是足够啦!

考虑最终的切法长这样:

那么平行四边形的面积就是 $ad+bc$
设面积为$i$的答案为 $ans(i)$,$x$ 的约数个数为 $d(x)$
那么就可以得到: $ans(i) = \sum {[ad + bc = i]} = \sum {[x + y = i]} \cdot d(x) \cdot d(y)$
然后看一眼就能发现这货是个卷积的形式,于是搞一波FFT就可以啦!