ARC117 - Zero-Sum Ranges 2

题目大意：计算由 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 构成的序列，且 包含恰好 \(k\) 个和为零的区间 的数量

显然需要转化为前缀和，通过前缀和相等的二元组数确定和为0的数量

而恰好 \(n\) 个 \(+1,-1\) 可以转化为 \(s_{2n}=0\)

设 \(m=2n+1\) ，接下来我们要计算 \(m\) 个元素，且 \(s_1=s_m=0,s_{i}=s_{i-1}\pm 1\) 的序列

\(s_i\) 的变化是连续的，考虑分为 \(s_i\ge 0,s_i<0\) 的两部分

以 \(\ge 0\) 为例，从高到低确定每个连续的峰折线的情况，折线组的位置不重要，只需要知道个数

令 \(dp_{i,j,c}\) 表示当前 \(i\) 个元素确定，且已经确定的元素分成了 \(j\) 段，得到 \(c\) 个相同对的方案数

每个段中可能包含折线组，且两端一定是当前的最低值，状态数为 \(O(n^4)\)

每次 \(dp\) 在当前状态上扩展下一层的情况，由于变化连续，得到新的状态

1.每个段两边应该出现新的位置

2.两个段向两边扩展时，可能共用一个位置

3.可能出现新的峰顶

根据2,3的情况，组合数转移

如果直接枚举2,3情况，复杂度为 \(O(n^6)\)

实际上容易发现2,3情况可以放在一起处理

具体的，对于新出现的 \(j+1\) 个位置（也就是每两个段之间的间隔）是一定会出现的，用这 \(j+1\) 个可以合并为一整个段

剩余的情况，额外插入一个元素，就是在 \(j+1\) 个位置中分配，且每额外加入一个就能额外产生一个新的段

复杂度为 \(O(n^5)\)

最终合并 \(s_i\ge 0,s_i<0\) 的两部分，由于 \(s_1=s_m=0\) ，所以开头结尾两端必须是0，然后两部分的段交替排列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
enum{N=62};
int n,m,k;
ll C[N][N],dp[N][N][910];
// dp[i][j][s]
// i places taken
// j elements 
// s ranges generated
int D2(int n){ return n*(n-1)/2; }
int main() {
	scanf("%d%d",&n,&k),m=n*2+1;
	rep(i,0,m) rep(j,*C[i]=1,i) C[i][j]=C[i-1][j]+C[i-1][j-1];
	rep(i,0,m) if(D2(i)<=k) dp[i][i][D2(i)]=1;
	rep(i,1,m) rep(j,1,i) rep(s,0,k) if(dp[i][j][s]) {
		rep(d,j+1,m-i) {
			if(s+D2(d)>k) break;
			dp[i+d][d-j][s+D2(d)]+=dp[i][j][s]*C[d-1][j];
		}
	}
	ll ans=0;
	rep(i,1,m) rep(j,1,i) rep(s,0,k) if(dp[i][j][s]) {
		ans+=dp[i][j][s]*dp[m-i][j-1][k-s];
	}
	printf("%lld\n",ans);
}