[bzoj 3771] Triple

n件可区分的物品, 每件有价值wi. 无顺序地取出1, 2, 或3件, 求每种价值的方案数. (wi≤4*10^4) 设价值wi的物品有ai件.

令, , . 是每件物品取两次的方案数, 是每件物品取三次的方案数.

只取一件的方案数: .

取两件的方案数: . 因为将(x,y)算了2次, (x,x)算了1次.

取三件的方案数: . 因为将(x,y,z)算了6次, (x,x,y)算了3次, (x,x,x)算了1次. 减掉后, (x,x,x)算了1-3=-2次, 加上便将所有不合法的方案消去.

这道题先前写过, 经历和这位博主很像......看完题光顾着笑了, 谁知河神真的会拿一把, 两把, 或三把斧头......

实现的时候将都DFT, 做完所有运算, 再IDFT回去.

尝试推广......