每次遇到这种奇奇怪怪的 d p dp dp都不会做……
题目大意
给定 n , k n,k n,k，问你有多少个长度为 2 n 2n 2n的序列 { a 2 n } \{a_{2n}\} {a2n?}，满足 ? 1 ≤ i ≤ 2 n , i ∈ Z , a i ∈ { 1 , ? 1 } \forall 1\le i\le 2n,i\in \mathbb Z,a_i\in\{1,-1\} ?1≤i≤2n,i∈Z,ai?∈{1,?1}， 1 1 1和 ? 1 -1 ?1的个数都为 n n n， ∑ i = l r a i = 0 \sum_{i=l}^ra_i=0 ∑i=lr?ai?=0的对数恰好为 k k k
题解
设
s
i
=
∑
j
=
1
i
a
i
,
s
0
=
0
s_i=\sum_{j=1}^ia_i,s_0=0
si?=∑j=1i?ai?,s0?=0，把它画成图像，答案就是每条平行线和图像交点个数
k
k
k，
k
(
k
?
1
)
2
\frac{k(k-1)}{2}
2k(k?1)?的和
我们考虑从上到下刻画这个图像，顺便用
d
p
dp
dp求解答案，设
f
s
i
z
e
,
c
n
t
,
h
o
l
e
f_{size,cnt,hole}
fsize,cnt,hole?，
s
i
z
e
size
size表示已经用了的点的个数，
c
n
t
cnt
cnt表示当前
s
l
=
s
r
s_l=s_r
sl?=sr?的对数，
h
o
l
e
hole
hole表示相同高度中间需要补上的洞的个数
像上面这个图，就有
s
i
z
e
=
8
,
c
n
t
=
6
,
h
o
l
e
=
1
size=8,cnt=6,hole=1
size=8,cnt=6,hole=1，注：洞并没有算两边的空缺
考虑转移，枚举下一层结点数
x
x
x，就有
f
(
s
i
z
e
,
c
n
t
,
h
o
l
e
)
(
x
?
1
h
o
l
e
+
1
)
→
f
(
s
i
z
e
+
x
,
c
n
t
+
x
(
x
?
1
)
2
,
x
?
h
o
l
e
?
2
)
f(size,cnt,hole)\binom{x-1}{hole+1}\rightarrow f(size+x,cnt+\frac{x(x-1)}{2},x-hole-2)
f(size,cnt,hole)(hole+1x?1?)→f(size+x,cnt+2x(x?1)?,x?hole?2)，前面的系数是因为
x
x
x个数要放入
h
o
l
e
+
2
hole+2
hole+2个位置，且每个位置不能不放，用一个插板法就能理解，新的洞数考虑有
h
o
l
e
+
2
hole+2
hole+2必须要放进去，之后每放一个都会多一个洞
这样
d
p
dp
dp完以后还不是答案，这个只是从上往下的，我们考虑上下合并求出所有，由于从上到下和从下到上是对称的，所以不需要再
d
p
dp
dp一次，考虑让高度
≥
0
\ge0
≥0的和高度
<
0
<0
<0的合并，大概就是枚举上面的情况，会有
f
(
s
i
z
e
,
c
n
t
,
h
o
l
e
)
f
(
2
n
+
1
?
s
i
z
e
,
k
?
c
n
t
,
h
o
l
e
?
1
)
f(size,cnt,hole)f(2n+1-size,k-cnt,hole-1)
f(size,cnt,hole)f(2n+1?size,k?cnt,hole?1)的贡献，要特判所有点都在上方的情况
上面的图都是嫖官方题解的