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，然后两部分的段交替排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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);
}