command_block 的博客

command_block 的博客

[DP记录]ARC117E Zero-Sum Ranges 2

posted on 2021-10-29 08:29:08 | under 记录 |

题意 : 求出满足下列条件的序列 $A$ 的数目 :

  • $A$ 含有 $n$ 个 $+1$ 和 $n$ 个 $-1$ 。
  • 恰有 $k$ 个 $[l,r]$ 满足 $\sum A[l,r]=0$ 。

    $n\leq 30,k\leq n^2$ ,时限$\texttt{5s}$。


考虑 $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)$ ,可以通过。

#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;
}