题目
题目描述
一个序列的子序列如果是合法括号序列，就称其为 “合括子序列” 。如果一个序列的所有 “合括子序列” 中的最长者，长度恰为
2
k
2k
2k ，则该序列是 “好的” 。求长度为
n
n
n 的 “好的” 序列个数。
数据范围与提示
数据组数
T
≤
2
×
1
0
5
T\le 2\times 10^5
T≤2×105 ，数据范围
2
k
≤
n
≤
2
×
1
0
5
2k\le n\le 2\times 10^5
2k≤n≤2×105 。
思路
首先要进行一个转换。设 ( 为
+
1
+1
+1 ，) 为
−
1
-1
−1 ，设前缀和为
s
i
s_i
si ，则 “合括子序列” 最长者的长度为
n
−
s
n
+
2
min
i
=
1
n
s
i
n-s_n+2\min_{i=1}^{n}s_i
n−sn+2i=1minnsi
理由很简单。在
s
i
≥
0
s_i\ge 0
si≥0 的情况下，左括号多，必然可以全部匹配。出现问题肯定是第一个
s
i
=
−
1
s_i=-1
si=−1 。此时你可以 重新设置零点，因为这个 ) 是无用的，如果
s
s
s 只统计使用了的括号，后面的
s
s
s 实际上都要
+
1
+1
+1 才对。于是乎，后面即使再出现
s
j
=
−
1
s_j=-1
sj=−1 也是完全匹配的情况。下一个转折点是
s
j
=
−
2
s_j=-2
sj=−2 ，又可以重新设置零点。一共有
∣
min
s
i
∣
|\min s_i|
∣minsi∣ 个转折点，也就有这么多个右括号没有被用到。
最后一截还可能剩余了左括号。最后的剩余左括号数量是 s n s_n sn 吗？错，是 s n + ∣ min s i ∣ s_n+|\min s_i| sn+∣minsi∣ 才对。别忘了我们重新设置了零点的。显然 s n + ∣ min s i ∣ s_n+|\min s_i| sn+∣minsi∣ 为非负整数。所以 n n n 减去二者即是 n − s n − 2 ∣ min s i ∣ n-s_n-2|\min s_i| n−sn−2∣minsi∣ 为 “合括子序列” 最长的长度。考虑到 min s i ≤ 0 \min s_i\le 0 minsi≤0 就把绝对值符号去掉了而已。
有了这个式子，考虑枚举
t
=
min
s
i
t=\min s_i
t=minsi ，此时必然需要
s
n
=
n
−
2
k
+
2
t
s_n=n-2k+2t
sn=n−2k+2t
如何计算方案数？把
s
i
s_i
si 随
i
i
i 变化的图像画出来，再把坐标系旋转
4
5
∘
45^{\circ}
45∘ ，这不就是格点图内的移动吗？终止点是
(
n
−
s
n
2
,
n
+
s
n
2
)
(\frac{n-s_n}{2},\frac{n+s_n}{2})
(2n−sn,2n+sn) 。而
t
t
t 的限制成为了不能越过
y
=
x
+
t
y=x+t
y=x+t 这条直线，且必须碰触一次。卡特兰的变形嘛。方案数
(
n
(
n
+
s
n
)
/
2
)
−
(
n
(
n
+
s
n
)
/
2
−
t
+
1
)
{n\choose (n+s_n)/2}-{n\choose (n+s_n)/2-t+1}
((n+sn)/2n)−((n+sn)/2−t+1n)
别忘了
s
n
s_n
sn 和
t
t
t 并不是独立的。将
s
n
s_n
sn 用
t
t
t 替换，你会惊讶的发现第二个组合数内的
t
t
t 消失了！
(
n
n
−
k
+
t
)
−
(
n
n
−
k
+
1
)
{n\choose n-k+t}-{n\choose n-k+1}
(n−k+tn)−(n−k+1n)
为了确保碰触一次，减去没能越过
y
=
x
+
t
+
1
y=x+t+1
y=x+t+1 这条直线的方案数，即
(
n
k
−
t
)
−
(
n
n
−
k
)
{n\choose k-t}-{n\choose n-k}
(k−tn)−(n−kn) 后，我们知道了
t
=
min
s
i
t=\min s_i
t=minsi 的方案数是
(
n
k
)
−
(
n
k
−
1
)
{n\choose k}-{n\choose k-1}
(kn)−(k−1n)
你没看错，跟
t
t
t 无关！而
t
t
t 的取值是多少呢？只要
y
=
x
+
t
y=x+t
y=x+t 能在
(
0
,
0
)
(0,0)
(0,0) 去
(
n
−
s
n
2
,
n
+
s
n
2
)
(\frac{n-s_n}{2},\frac{n+s_n}{2})
(2n−sn,2n+sn) 的路径中出现就可以。也就是
f
(
n
−
s
n
2
)
∈
[
0
,
n
+
s
n
2
]
f(\frac{n-s_n}{2})\in[0,\frac{n+s_n}{2}]
f(2n−sn)∈[0,2n+sn] 且
f
(
0
)
≤
0
f(0)\le 0
f(0)≤0 。解出
2
k
−
n
≤
t
≤
0
2k-n\le t\le 0
2k−n≤t≤0
进而 t t t 的取值数量是 n − 2 k + 1 n-2k+1 n−2k+1 ，乘以每个 t t t 的方案数就是答案了。竟然是 O ( 1 ) \mathcal O(1) O(1) 计算，这难道不令人啧啧惊奇吗？
代码
输出 ( n − 2 k + 1 ) ( C n k − C n k − 1 ) (n-2k+1)(C_{n}^{k}-C_{n}^{k-1}) (n−2k+1)(Cnk−Cnk−1) 你都不会么？