「BZOJ1037」[ZJOI2008]生日聚会Party

Description

今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件:

对于任意连续的一段,男孩与女孩的数目之差不超过kk

很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题……

假设参加party的人中共有nn个男孩与mm个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以1234567812345678的余数。

Input

仅包含一行共33个整数,分别为男孩数目nn, 女孩数目mm, 常数kk

Output

应包含一行,为题中要求的答案。

Sample Input

1
1 2 1

Sample Output

1
1

HINT

对于30%30\%的数据,nn , m20m \leq 20
对于100%100\%的数据, nn , m150m \leq 150k20k \leq 20

Solution

fi,j,k,lf_{i,j,k,l}
ii个人,男有jj个,女有kk个,差距k\leq k的方案数
优化一下
ii个人,男有jj个,女有iji-j个,差距k\leq k的方案数
但是考虑fi+1f_{i+1}的时候,加男加女无法判断k+1k+1还是k1k-1

换一个方程

fi,j,x,yf_{i,j,x,y}
ii个人,男有jj个,女有iji-j个, 男-女最大差距为xx,女-男最大差距为yy
这样在加男女的时候就可以判断最大差距是变大还是变。
最大差距指iij[1,i1]j\in [1,i-1][j,i][j,i]的最大差距,一定跟ii相关的。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

int n, m, t;
const ll p = 12345678;
ll f[2][160][22][22];
void add(ll &x, ll v) {
x += v;
if(x >= p) x %= p;
}
int tot;
int main() {
n = read(), m = read(), t = read();
tot = n + m;
ll ans = 0;
f[0][0][0][0] = 1;
int c = 0;
for(int i = 1; i <= tot; ++i) {
c ^= 1;
memset(f[c], 0, sizeof f[c]);
for(int j = 0; j <= i - 1 && j <= n; ++j) {
int k = i - 1 - j;
if(k > m) continue;
for(int x = 0; x <= t; ++x) {
for(int y = 0; y <= t; ++y) if(f[c ^ 1][j][x][y]){
if(j + 1 <= n)
add(f[c][j + 1][x + 1][max(0, y - 1)], f[c ^ 1][j][x][y]);
if(k + 1 <= m)add(f[c][j][max(0, x - 1)][y + 1], f[c ^ 1][j][x][y]);
}
}
}
}
for(int i = 0; i <= t; ++i)
for(int j = 0; j <= t; ++j)
add(ans, f[c][n][i][j]);
writeln((ans + p) % p);
return 0;
}