求助01背包
  • 板块学术版
  • 楼主19ty02
  • 当前回复18
  • 已保存回复18
  • 发布时间2021/3/30 20:43
  • 上次更新2023/11/5 01:21:17
查看原帖
求助01背包
264851
19ty02楼主2021/3/30 20:43

RT，蒟蒻求助如何用多项式优化01背包方案数，即求：

f(x)=∏i=1n(1+xai)f(x)=\prod_{i=1}^n(1+x^{a_i})

其中 n≤2∗105,∑ai≤2∗105n\leq 2*10^5,\sum a_i\leq 2*10^5。

2021/3/30 20:43