题解：P12416 多项式高手
Purslane
·
·
题解
Solution
哎我刚开始把这个题想的太简单了，过一会发现又把它想的太难了 （主要是看到其他人的代码很短）。
前置知识：O(n \sqrt n) 求 1 到 n 的划分数，即对 n_0 = 1,2,\cdots,n 求出 \sum a_i = n_0，a_i \le a_{i+1} 的 a 的组数。
对应这种拆分问题考虑使用 Ferrers 图辅助理解。比如这样：
考虑这张图的最大内接正方形，假设边长为 h。
则可以将图形分为 h \times h 的正方形和两个最大值 \le h 的整数拆分。所以我们可以得到生成函数为：
\sum_{h \ge 1} x^{h \times h} \prod_{j=1}^h (\dfrac{1}{1-x^j})^2
显然 h 的值域是 O(\sqrt n) 的。而后面那个乘积的组合意义是：对于每个权值为 1 到 h 的物品，做两遍完全背包（这一步很巧妙，可以直接规避卷积操作。换句话说，在 DP 的过程中已经把卷积做了一遍。）。这样我们可以 O(n) 的完成 h \leftarrow h+1 的变化。
代码长这样：
ffor(h,1,B) {
ffor(i,h,m) dp[i]=(dp[i]+dp[i-h])%MOD;
ffor(i,h,m) dp[i]=(dp[i]+dp[i-h])%MOD;
ffor(j,h*h,m) cnt[j]=(cnt[j]+dp[j-h*h])%MOD;
}
回到这道题。数据保证了：要么 $n$ 极其小可以爆搜（$n=2$），要么 $n \le m \le 2n-1$。
将题目改为：有 $n$ 个物品，第 $i$ 个物品的权值为 $\sum_{j=n-i+1}^n b_j$，大小为 $i$。选出若干个物品，使得物品大小和为 $m$。每组方案的权值为所有物品权值之和。求出方案权值之和。
有一个比较直接的思路：对于每个 $i$ 和 $t$，求出有多少种方案能包含至少 $t$ 个 $i$ 物品。而他等于 $m-it$ 的划分数（可以构建双射。但是这个结论真的对吗？）
写出代码（其中 `suf` 数组表示后缀和）
```cpp
ffor(j,1,n) ffor(t,1,m/j) ans=(ans+1ll*cnt[m-j*t]*suf[n-j+1])%MOD;
```
注意，$m-it$ 划分的时候，有可能会选出大小大于 $n$ 的数！所以这个双射不满足。
不过很容易修正——那些不符合要求的情况，可以直接对应为 $m-(n+1)$，$m-(n+2)$，$\cdots$，$1$（考虑删掉最大的物品。而删去最大的物品之后，$m' \le n$ 所以不会出现不合法的情况了！）
再对 `cnt` 数组套一个前缀和即可。
代码：
```cpp
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,B=330,MOD=1e9+7;
int n,m,b[MAXN],suf[MAXN];
int cnt[MAXN],dp[MAXN],pre[MAXN];
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
ffor(i,1,n) cin>>b[i];
roff(i,n,1) suf[i]=(suf[i+1]+b[i])%MOD;
if(n==2) {
int ans=0;
ffor(j,0,m) if(j<=m-j) ans=(ans+1ll*b[1]*j%MOD+1ll*b[2]*(m-j))%MOD;
return cout<<(ans%MOD+MOD)%MOD,0;
}
pre[0]=cnt[0]=dp[0]=1;
ffor(h,1,B) {
ffor(i,h,m) dp[i]=(dp[i]+dp[i-h])%MOD;
ffor(i,h,m) dp[i]=(dp[i]+dp[i-h])%MOD;
ffor(j,h*h,m) cnt[j]=(cnt[j]+dp[j-h*h])%MOD;
}
int ans=0;
pre[0]=1;
ffor(i,1,m) pre[i]=(pre[i-1]+cnt[i])%MOD;
ffor(j,1,n) ffor(t,1,m/j) ans=(ans+1ll*cnt[m-j*t]*suf[n-j+1])%MOD;
m-=n+1;
ffor(j,1,n) ffor(t,1,m/j) ans=(ans-1ll*pre[m-j*t]*suf[n-j+1])%MOD;
cout<<(ans%MOD+MOD)%MOD;
return 0;
}
```