Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

05/17
20:54
一般动规与递推 中国剩余定理 容斥原理 组合数/lucas

[bzoj 3782] 上学路线

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行,四个整数N、M、T、P。
接下来的T行,每行两个整数,表示施工的路口的坐标。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一行,一个整数,路径数mod P的值。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 4 3 1019663265
3 0
1 1
2 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

8

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1<=N,M<=10^10
0<=T<=200
p=1000003或p=1019663265

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

容斥原理dp,先把终点当做障碍点,把所有障碍点按照x为第一关键字,y为第二关键字从小到大排序

设f[i]为到达第i个障碍点且不经过任何点的方案数,设G[i][j]为从第i个障碍点走到第j个障碍点的方案数

从(x1, y1) 走到 (x2, y2) 的方案数为 C(x1 + y1 - x2 - y2, x1 - x2),这个用lucas定理求

f[i] = G[0][i] - sigma(G[j][i] *f[j])

p=1000003的时候直接求

p=1019663265的时候先分解质因数然后用CRT合并

 

[bzoj 3782] 上学路线