CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== Fly ======

==== 题意 ====

给定一个长度为 $n$ 的数列 $a_i$ 和 $k$ 个限制形如 $(b_i,c_i)$ 和一个数 $m$ ，求有多少个数列 $x_i$ 满足 $\sum{a_ix_i}\le m$ 且 $x_{b_i}\& 2^{c_i}=0$ 。

$n\le 4*10^4, m\le 10^{18}, k\le 5*10^3, \sum{a_i}\le 4*10^4, b_i\le n, c_i<60, MOD=998244353$
==== 题解 ====

我们发现限制是对于每个 $x_i$ 的二进制位进行的，所以考虑直接将 $a_ix_i$ 分成 $\sum{a_i2^ky_{i,k}}$ ，其中 $y_{i,k}$ 表示 $a_i2^k$ 是否被选择了。这样我们就把问题转化成了 $a_i2^k$ 这共 $60n$ 个物品，其中有 $k$ 个物品被强制不能选择时，选择的物品的总和不超过 $m$ 的方案数。

注意到 $m$ 非常大，所以直接做背包是没有前途的。这时候我们注意到 $a_i2^k$ 这样的一个物品是不会影响到总和的二进制最低的 $k$ 位的，所以我们考虑按照 $2^0$ 到 $2^{59}$ 这个顺序来对这些物品进行DP。

我们定义 $dp_{i,j,0/1}$ 表示已经选完 $2^i$ 一类的物品，总和 $S$ 满足 $\lfloor \frac{S}{2^{i+1}} \rfloor = j$ ，且 $S\%2^{i+1}$ 是否严格大于 $m\%2^{i+1}$ 的方案数。


考虑先分析一下第二维的范围，我们假设 $\sum{a_i}=SA$ ，已经选完 $2^k$ 的物品时，$S\le \sum_{i=0}^{k}{2^iSA}\le 2^{k+1}SA$ ，所以第二维最多也就是 $SA$ 。同时我们也可以发现这时候直接DP还是没啥前途。

考虑对于每一类物品一起算，利用生成函数显然就是 $\prod_{i=1}^{n}{[(i,k)\notin (b,c)](1+x^{2^ka_i})}$ ，进行变化可以变为 $\prod_{i=1}^{n}{(1+x^{2^ka_i})*(\prod_{(i,k)\in (b,c)}{(1+x^{2^ka_i})})^{-1}}$ 。我们考虑将其中的 $x^{2^k}$ 变为 $x$ ，因为对于每个 $2^k$ 我们可以发现剩余的部分是完全相同的。前面的部分设为 $g(x)=\prod_{i=1}^{n}{(1+x^{a_i})}$ ，后面的部分我们考虑对每个 $2^k$ 我们做一次反向的背包来得到最终的式子，设其为 $G(x)$ 。

我们注意到，对于 $[x^i]G(x)$ 和 $dp_{k-1,j,0/1}$ ，我们可以得到新的第二维是 $\lfloor \frac{2^ki+2^kj+Y}{2^{k+1}} \rfloor=\lfloor \frac{i+j}{2} \rfloor$ ，其中 $Y$ 是上一次的余数。第三维我们可以按照前面的 $0$ 到 $k-1$ 位是否严格大于 $m$ 来进行讨论，严格大于则当前位只需要大于等于就可以大于，否则当前位要严格大于。

考虑对于每个 $2^k$ 得到 $G(x)$ 之后怎么结合 $dp_{k-1}$ 来得到 $dp_{k}$ 。我们分两类来转移，$dp_{k,\lfloor \frac{X}{2} \rfloor,[X\&1>m_k]}=\sum_{i+j=X}{[x^i]G(x)*dp_{k-1,j,0}}$ 和 $dp_{k,\lfloor \frac{X}{2} \rfloor,[X\&1\ge m_k]}=\sum_{i+j=X}{[x^i]G(x)*dp_{k-1,j,1}}$ 。这两类分别做一次卷积即可。

最后我们的答案就是 $dp_{59,0,0}$ ，我实现略微卡常。
CVBB ACM Team

用户工具

站点工具

页面工具
