BZOJ-3771. Triple

这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 n 个物品,第 i 个物品的价值为 x_i(0 < x_i \leq 4\cdot10^4),问在这 n 个物品中选出 1 个或 2 个或 3 个价值和是多少,对于每个价值求出方案个数,在这题中 (a, b)(b, a) 算作一种方案

例如有三个物品

x_1 x_2 x_3
1 2 3

选一个就可以得到 1, 2, 3 三种价值

选两个就可以得到 1+2, 1+3, 2+3 三种价值

选三个就可以得到 1+2+3 一种价值

所以最后答案就是

价值 1 2 3 4 5 6
方案数 1 1 2 1 1 1

这题可以先用母函数表示出选一个的方案(系数是物品出现次数,指数是物品价值)

 A(x) = x^1 + x^2 + x^3

然后由于多项式乘法会将系数相乘,指数相加,将两个这样方案的母函数 A(x), B(x) 相乘就相当于在 A(x) 表示的物品中选出一个再在 B(x) 表示的物品中选出一个,组合起来

所以不考虑重复,在物品中选出三个的方案就是 \frac{1}{6}A^3(x)

现在用 B(x), C(x) 分别表示一种物品选了 2 次和 3 次的方案

 B(x) = x^2 + x^4 + x^6 \\ C(x) = x^3 + x^6 + x^9

选三个有可能是 AAB, ABA, BAA, AAA 这几种重复情况,所以扣掉后方案就是

\frac{A^3(x) - 3A(x)\cdot B(x) + 2C(x)}{6}

选两个的方案是

\frac{A^2(x)-B(x)}{2}

选一个的方案是

A(x)

加起来后就会得到总的方案

由于这里用到了多项式乘法,用FFT优化即可

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/04/bzoj-3771

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “BZOJ-3771. Triple

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.