一类dp优化——统计答案优化

这个名字可能挺抽象的，没想到什么好名字。

这类 $dp$ 的特征是：有一维状态不参与转移的系数，只是转移的时候改变本身的位置，这维状态仅用来统计答案而设立。

例如经典分段形式的 $dp$ ，求方案数我们都会朴素的 $O(n^2)$ ，设 $f_i$ 是以 $i $ 作为段尾的方案数，转移枚举上一段的结尾。

但是如果每个方案对答案的贡献都是其段数或是一个关于段数的常系数多项式，那我们就需要多开一维 $f_{i,k}$ 表示以 $i $ 作为段尾，段数 $k$ 的方案数。

转移的柿子不变，这个 $k$ 不参与转移柿子，只是转移过去默默加了个 $1$ ，在统计答案的时候起到作用。

（每次 $i$ 发生变化的时候，所有 $k$ 都拖家带口地转移到 $k+1$ ，对答案“额外”产生 $(k+1)-k=1$ 的贡献。）

这个时候我们可以设 $f'_i$ 为 $\sum_kf_{i,k}$ ，也就是原来的方案数，每次转移的时候将答案数组加上这个额外的贡献，就做出来了。

可以理解为将这 $k$ 段的贡献均摊到每段中转移了。

这种优化你瞪不出来柿子里的前缀和或是什么其他数据结构优化，你唯一能瞪出来的是，有一维状态没用，只在统计答案的时候有用。

这个时候我们通常可以将这一维状态的和设为新状态，压掉一维，而对答案的贡献以及转移时的小细节需要自行处理。

（通常的套路是设一个“和状态”或者一个“答案贡献状态”，然后你把新状态代进原来的转移和答案贡献里面，如果很好做，那就成功了。）

搞一个进阶的：分段 $dp$ ，贡献是段数的平方。

还是设 $f'_i=\sum_kf_{i,k}$ ，转移的时候对答案额外增加的贡献是 $(k+1)^2-k^2=2k+1$ ，还是有 $k$ ，所以我们还要维护 $\sum_kkf_{i,k}$ ，维护方式前文提到了。

这其实是一种逆推的方式，见的惯了直接把所有常数次方设出来顺着推即可。

再来看一个例子：

x=read();n=read();p=(db)read()/100;
f[0][0][0]=1;
F(i,0,n-1) F(j,0,n-1) F(k,0,n-j) {
    f[i+1][j+1][k]+=f[i][j][k]*(1-p);
    if(j&1) ans+=f[i][j][k]*p*k;
    else f[i+1][j/2][k+1]+=f[i][j][k]*p;
} F(j,0,n) F(k,0,n) ans+=f[n][j][k]*(ctz(x+j)+k);

可以优化成：

x=read();n=read();p=(db)read()/100;
f[0][0]=1;
F(i,0,n-1) F(j,0,n-1) {
    f[i+1][j+1]+=f[i][j]*(1-p);
    if(!(j&1)) ans+=f[i][j]*p,f[i+1][j/2]+=f[i][j]*p;
} F(j,0,n) ans+=f[n][j]*ctz(x+j);

不需要看原题，只需要你看到这个转移的柿子，发现 $k$ 这维完全不参与转移，只是每次贡献答案的时候作为系数出现。

所以我们设 $f'_{i,j}=\sum_kf_{i,j,k}$ ，最后的系数乘上了 $k$ ，所以我每次 $k'\gets k+1$ 的时候更新答案。

理解起来可能有些抽象，不过是有一定套路成分在的。

如果 $k$ 对答案的贡献是高次多项式，那么你需要将所有低次项的和全部设出来，类似于线段树维护区间加区间常数次方和。

构造性问题是难的，判定性问题是容易的，考场上如果凭着直觉（亦或是自己也不理解为什么正确的套路）写出了良好的状态构造，那么剩下的不过是简单的判定。

刚刚的例子是CF441E Valera and Number。