[DP记录]ARC117E Zero-Sum Ranges 2
command_block
2021-10-29 08:29:08
**题意** ： 求出满足下列条件的序列 $A$ 的数目 ：
- $A$ 含有 $n$ 个 $+1$ 和 $n$ 个 $-1$ 。
- 恰有 $k$ 个 $[l,r]$ 满足 $\sum A[l,r]=0$ 。
$n\leq 30,k\leq n^2$ ，时限$\texttt{5s}$。
------------
- 参考资料[一类基于笛卡尔树的排列计数DP](https://www.luogu.com.cn/blog/command-block/yi-lei-ji-yu-duan-di-pai-lie-ji-shuo-dp)
考虑 $A$ 的前缀和 $S$ ，记 $O_i=\sum\limits_{j=0}^{2n}[S_j=i]$ ，则 $\sum\limits_{i}\dbinom{O_i}{2}$ 就是和为 $0$ 的区间数目。
考虑从大到小（从下往上，即按照水淹笛卡尔树的顺序）填写 $S$ 。
记 $dp_{i,j,k,c}$ 表示填写了 $i$ 个位置，目前分为 $j$ 段，目前填写了 $k$ 层，且目前的 $\sum\limits_{i}\binom{O_i}{2}$ 为 $c$ 的方案数。
计算答案时，由于强制要求 $S_0=S_{2n}=0$ ，考虑对 $S<0$ 和 $S\geq 0$ 进行拼接。
具体地，拼接时一定是一段 $<0$ 一段 $\geq 0$ 交错，记 $g_{i,j,c}$ 为（由于对称性，正负部分的方案数是一样的）分为 $j$ 段，占用 $i$ 个位置， $\sum\limits_{i}\binom{O_i}{2}$ 为 $c$ 的方案数，则答案为
$${\rm ANS}=\sum\limits_{i,j,c}g_{i,j,c}\times g_{2*n+1-i,j-1,k-c}$$
然后可以发现，我们只关心段数而不关心层数，所以可以将 $dp_{i,j,k,c}$ 中的 $k$ 省去，按照 $c$ 从大到小转移即可。
对于 $dp_{i,j,c}$ ，向上加一层，可能出现下列情况 ：
- 某个段间隙被连接，需要占用一个位置，且会使得两个段合成一个
- 某个段间隙未连接，（由于 $S$ 的变化连续）需要左右各占用一个位置来扩展
- 加入新的“山谷”
枚举新一层加入数的个数 $x$ ，则有 ：
$$dp_{i+x,x-j,c+\binom{x}{2}}\leftarrow \dbinom{x-1}{j}dp_{i,j,c}$$
妙处在于 $x-j$ ：共有 $j+1$ 个间隙以供插入，考虑每个空位，若只放一个数，则使得两侧合并；若放 $a(\geq 2)$ 个，则先用两个贴在空位两侧，其余使得段数增加 $a-2$ 。不难得知新的段数为 $x-j$ 。
方案数等价于将 $x$ 个球放入 $j+1$ 个盒子，不允许空盒： $\dbinom{x-1}{j}$
复杂度为 $O(n^5)$ ，可以通过。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
ll dp[65][35][905],s[65][35][905],C[35][35];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
for (int i=0;i<=n+1;i++){
C[i][0]=1;
for (int j=1;j<=i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
for (int x=0;x<=n+1;x++)
if (x*(x-1)/2<=k)dp[x][x][x*(x-1)/2]=1;
for (int c=0;c<=k;c++)
for (int i=1;i<=n*2+1;i++)
for (int j=1;j<=min(n+1,i);j++)if (dp[i][j][c]){
ll now=dp[i][j][c];
for (int x=j+1;x<=n+1;x++){
int c2=c+x*(x-1)/2;
if (c2>k||i+x>2*n+1)continue;
dp[i+x][x-j][c2]+=C[x-1][j]*now;
}
}
for (int c=0;c<=k;c++)s[0][0][c]=1;
for (int i=1;i<=n*2+1;i++)
for (int j=1;j<=min(n+1,i);j++)
for (int c=1;c<=k;c++)
s[i][j][c]=s[i][j][c-1]+dp[i][j][c];
ll ans=0;
for (int j1=1;j1<=n+1;j1++)
for (int i1=0;i1<=2*n+1;i1++){
int i2=2*n+1-i1,j2=j1-1;
for (int c=0;c<=k;c++)
ans+=dp[i1][j1][c]*dp[i2][j2][k-c];
}
printf("%lld",ans);
return 0;
}
```