[bzoj 1037] [ZJOI2008]生日聚会Party

n男m女 (除性别外不可区分) 坐一排, 要求对于任意连续的一段, 男女数目之差 (的绝对值) 不超过k, 求方案数模12345678. (n,m≤150, k≤20) 先数学化. 令男孩为-1, 女孩为1, 则 "男女数目之差不超过k" 转化为 "和不大于k且不小于-k". 考虑一个一个加数. 新加入一个数, 也就新添加了一些后缀, 即原来所有后缀 (含空串) 末尾再加上这个新数. 需要保证这些后缀和均在[-k,k]的范围内, 这等价于最大后缀和≤k, 最小后缀和≥-k. 因此, 以 为状态, 表示 个-1, 个1, 最大后缀和为 , 最小后缀和为 , 向后更新即可:

看了其他人的做法, 发现状态数可以减少一些. 修改状态的定义, 令 . 反正更新的时候要取 / ......

先前没发觉, 可能是因为没把从里提出来......

#define F(i, j, a, b) f[i][j][a+k][b+k]

const int N = 150, K = 20, MOD = 12345678;

int f[N+1][N+1][2*K+1][2*K+1];

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	F(0, 0, 0, 0) = 1;
	
	rep (i, 0, n+1) rep (j, 0, m+1) {
		rep (a, -k, k+1) rep (b, -k, a+1) {
			int x, y, now = F(i, j, a, b);
			
			if (i < n) {
				x = max(a-1, -1), y = min(b-1, -1);
				if (x <= k && y >= -k)
					(F(i+1, j, x, y) += now) %= MOD;
			}
			if (j < m) {
				x = max(a+1, 1), y = min(b+1, 1);
				if (x <= k && y >= -k)
					(F(i, j+1, x, y) += now) %= MOD;
			}
		}
	}

	int ans = 0;
	rep (a, -k, k+1) rep (b, -k, k+1) (ans += F(n, m, a, b)) %= MOD;

	printf("%d\n", ans);

	return 0;
}