ARC117E零和范围2

ARC117E Zero-Sum Ranges 2

Converts an interval sum of zeros to a prefixed sum equal,Something like this：

The answer is obviously the number of layers per layer $k$,$\frac{k(k-1)}{2}$ 的和.

Consider going from top to bottom in layers DP,Note that the positions where the prefix sum is equal are necessarily not adjacent,And there is a peak or pit in the middle of both positions,The pit indicates that the next layer is required.

记 $f_{i,j,k}$ Indicates that there is currently available from top to bottom $i$ 个数,The equal pairs formed have $j$ 个,The holes to be filled are $k$ 个.

考虑转移,Enumerate the next layer to add $x$ 个数：$f_{i,j,k}\to f_{i+x,j+\frac{x(x-1)}{2},x-(k+2)}$,系数为 $C_{x-1}^{k+1}$（According to the plug-in method）.

Enumerate the variables and merge the upper and lower bounds of zero.

时间复杂度 $\mathcal{O}(n^5)$.

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long ll;

#define ha putchar(' ')
#define he putchar('\n')

inline int read() {
    
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
    
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x) {
    
	if (x < 0) {
    
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

int n, k, f[105][1005][105], c[105][105];

signed main() {
    
	n = read(), k = read();
	for (int i = 0; i <= n + 1; ++i) {
    
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j <= i; ++j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
	for (int i = 1; i <= 2 * n + 2; ++i) f[i][i * (i - 1) / 2][i - 1] = 1;
	for (int i = 0; i <= 2 * n + 2; ++i)
		for (int j = 0; j <= n * n + 1; ++j)
			for (int l = 0; l <= n + 2; ++l) {
    
				if (f[i][j][l] == 0) continue;
				for (int x = l + 2; x <= 2 * n + 2; ++x) {
    
					int nxt = j + x * (x - 1) / 2;
					if (nxt > k) break;
					f[i + x][nxt][x - (l + 2)] += f[i][j][l] * c[x - 1][l + 1];
				}
			}
	ll ans = f[2 * n + 1][k][0];
	for (int i = 0; i <= 2 * n + 1; ++i)
		for (int j = 0; j <= k; ++j)
			for (int l = 1; l <= n; ++l)
				ans += f[i][j][l] * f[2 * n + 1 - i][k - j][l - 1];
	write(ans), he;
	return 0;
}