题意
给定一个
h
h
h行
w
w
w列的方格，其中有
n
n
n个格子不能走，问只向下或向右一共有多少种方案从左上角走到右下角。
h
,
w
≤
1
e
5
h,w \le 1e5
h,w≤1e5
n
≤
2000
n \le 2000
n≤2000
题解
发现
h
,
w
h,w
h,w很大
n
n
n很小，于是考虑利用不能走的格子dp。
易知通过一个
a
×
b
a \times b
a×b 的放格有
C
a
+
b
?
2
b
?
1
C^{b-1}_{a+b-2}
Ca+b?2b?1? 种方案，则考虑设计
f
i
f_{i}
fi?表示从左上角到第i个不可走的格子，途中不经过任何不可走的格子的方案数。将所有不可走的格子按x第一优先y第二优先递增排序，得出状态转移方程：
f
i
=
f_{i} =
fi?=
C
x
i
+
y
i
?
2
x
i
?
1
?
C^{x_{i}-1}_{x_{i}+y_{i}-2} -
Cxi?+yi??2xi??1??
∑
j
=
0
i
?
1
j
×
\sum_{j=0}^{i-1} j \times
∑j=0i?1?j×
C
x
i
+
y
i
?
x
j
?
y
j
x
i
?
x
j
C^{x_{i}-x_{j}}_{x_{i}+y_{i}-x_{j}-y_{j}}
Cxi?+yi??xj??yj?xi??xj??
将右下角的格子看做第
n
+
1
n+1
n+1个不可通行格子，
f
n
+
1
f_{n+1}
fn+1?即为答案
PS：排序后从左上角到
i
i
i 的路线内可能经过的不可通行的格子编号全部小于
i
i
i 。
|