2022-2023:teams:kunkunkun:2022-nowcoder-1
| 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:kunkunkun:2022-nowcoder-1 [2022/08/12 20:01] sd_ltt 创建 |
2022-2023:teams:kunkunkun:2022-nowcoder-1 [2022/08/31 15:42] (当前版本) purplewonder |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| ===== G-Lexicographical Maximum ===== | ===== G-Lexicographical Maximum ===== | ||
| 签到题 | 签到题 | ||
| + | |||
| + | ===== H ===== | ||
| + | |||
| + | **题目大意：n种物品每种有无数个，第i个物品的体积为$a_i$，求解选择物品总体积不超过m的方案数** | ||
| + | |||
| + | **此外，有k个限制，第i个限制形如第$b_i$个物品所选的数量二进制表示下从低到高第$c_i$位必须为0** | ||
| + | |||
| + | **首先，进行二进制分组，将$n$种物品拆分为$logm$组物品，第$i$组物品中有$n$种物品，第$j$种物品的体积为$a_j*2^i$，总共有$n*logm$个物品，然后可以进行$0/1$背包** | ||
| + | |||
| + | **设$F(i,j,b)$表示，做完了前$i$组物品，选了体积为$V$的物品，满足$j=\lfloor\frac{V}{2^i}\rfloor,b=[(V\ mod\ 2^i)>(M\ mod\ 2^i)]$** | ||
| + | |||
| + | **发现$i$的最大值约为$logm$，$j$的最大值约为$2*n$，$b$只有$0/1$两种取值** | ||
| + | |||
| + | **设$g(i,j)$为第$i$组物品，选择了体积为$j*2^i$物品的方案数** | ||
| + | $$ | ||
| + | g(i,j)=[x^j]\frac{\prod_{l=1}^n(1+x^{a_l})}{\prod_{(l,i)\in Lim}(1+x^{a_l})} | ||
| + | $$ | ||
| + | **分子可以利用分治NTT预处理，对于所有的$i$都适用** | ||
| + | |||
| + | **对于每一个限制来说，可以对分子做一次反向$0/1$背包来处理，复杂度为$O(n*k)$** | ||
| + | |||
| + | **设$B(x,y,z)=[x>y||(x==y\&\&z)]$** | ||
| + | |||
| + | **对于当前的$F(i,j,b)$，设$m_i$为$m$在二进制下第$i$位的值，可以向后转移贡献：** | ||
| + | $$ | ||
| + | F(i,j,b)\times g(i,l)\rightarrow F(i+1,\lfloor\frac{j+l}{2}\rfloor,B((j+l)mod\ 2,m_i,b) | ||
| + | $$ | ||
| + | **可以枚举$i$和$b$，然后对$j$和$l$维度进行$NTT$卷积优化，再转移贡献，这部分复杂度为$O(nlognlogm)$** | ||
| + | |||
| + | **总复杂度为$O(nlog^2n+nk+nlognlogM)$** | ||
| + | |||
| + | ===== Replay ===== | ||
| + | |||
| + | 提前看了题解，于是摆了。主要是看队友切题。 | ||
2022-2023/teams/kunkunkun/2022-nowcoder-1.1660305664.txt.gz · 最后更改: 2022/08/12 20:01 由 sd_ltt
