With Passion and Love

CodeChef MGCHGYM

CodeChef MGCHGYM

Link

问题在于第3个询问操作,前面两个都是可以用平衡树直接维护的。

由于$K\leq 10$,这个题和BZOJ1042套路一样。

先对给出的询问离线,然后把所有$1$操作和给出的$w_i$离散化。

如果所有给出的东西都有无限个那么方案数可以用完全背包算出。

考虑一个区间内的贡献相当于是限制了每个物品的个数。

方案数容斥计算,用总方案数减去至少有一个超出限制的方案数然后加上至少两个超出的方案。

暴力枚举每一种子集,表示超出限制的个数,设为${S_i,d_i}$,用$S_i$表示物品的价值$d_i​$表示限制个数。

那么对于这种情况超出的方案数则为$dp[tot-\sum_{i} S_i(d_i+1)]$。



Leave a Reply

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