FFT 【JSOI2012】bzoj4332 分零食 （未解决） 很不错的一道倍增优化dp？？ 题目大意： 题目分析：
第一次做这类题挺难想的
题目大意：
有n个小朋友，m块糖。
给小朋友分糖，如果一个小朋友分不到糖，那他后面的小朋友也分不到糖。
每个小朋友有一个喜悦值，有三个参数，O，S，U，设一个小朋友分到糖数为x，则这个小朋友的喜悦值为O*x x+ S x +U，分不到糖的小朋友的喜悦值为1。
求所有分糖方案下 所有小朋友喜悦值乘积 的和。
题目分析：
首先想到 dp 。∑i=1ng[i][m]。
dp方程
g[n][m]=∑i=1mg[n−1][i]×f(m−i)
（枚举第 n 个小朋友分到的糖数）。
然后发现是个卷积的形式，于是立刻想到 FFT ，立刻想到倍增 （
g[n]=g[n−1]∗f
得到
g[n]=g[0]∗fn
，而 g[0]=1 所以
g[n]=fn
）。但是我们显然要求的是
∑i=1ng[i][m]
只是这样倍增显然是不行的。
于是记
F[n]=∑i=1ng[i]
则 2 的倍数）。
F[n]=∑i=1ng[i]
F[n]=F[n2]+∑i=n2+1ng[i]
F[n]=F[n2]+∑i=n2+1nfi
F[n]=F[n2]+∑i=1n2fi+n2
F[n]=F[n2]+fn2∑i=1n2fi
F[n]=F[n2]+g[n2]∗F[n2]
完成！
对于 log2n 级别的。
于是就可以开心的使用倍增完成，取膜可以在求完卷积时膜。
复杂度 )