一道计数类DP例题~~~
ps：P党似乎不多了……
我这只蒟蒻第一次写题解，而且计数类DP还是早上刚学的，现学现用，或者说是所谓的“浅谈”一番吧！况且这题写题解的人似乎并不多（大佬似乎不屑于光临此题）
进入正题
- 题目大意：扔给你一个h*w的棋盘，并给定n给不可以经过的格子的坐标，和（sang）蔼（xin）可（bing）亲（kuang）地让你计算从(1,1)开始走到(h,w)的合法路径的条数，答案对\(10^9+7\)取模。
看完题后，呵，简单，都做过过河卒这种题吧！递推在手，天下我有！！
大笑着，不经意间瞟了一下数据范围，笑容瞬间凝固……
- $1<=h,w<=10^{5},1<=n<=2000 $
啥玩意？
无奈，出门左转，逃！
够英明的选择，但还有更英明的选择——学习！没错，学习！
好的，依阁下高见，我来学习了。
孺子可教，吭吭，听好了(冒犯)：
倘若你成了超人，通过了之前无法逾越的格子，那么你走到终点的路径总数是可以用一个组合数搞出来的。不会？那就对了，接着看。从起点走到终点，你必然走了\(h-1\)步往下，\(w-1\)步往右，对吧？总步数就是\(h+w-2\) ,然后想想组合数，整条路径我走了\(h-1\)步往下，剩下\(w-1\)步就确定了。那么换种说法，我从\(h+w-2\)步中选\(h-1\)步往下，就可以确定唯一的一条路径，则总方案数为\(C_{h+w-2}^{h-1}\)种，同理，走\(w-1\)步往下，也可以确定唯一的一条路径，有\(C_{h+w-2}^{w-1}\)种方案数。两者等价。（等价？质疑请了解\(C_n^m=C_n^{n-m}\)）
但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案。
\[Ans=C_{h+w-2}^{h-1}-P_1+P_2-P_3+...+(-1)^n*P_n\]
其中\(P_i\)表示经过i个不能走的点的路径，但是，此题n<=2000，容斥原理直接炸掉。（况且我也不会容斥原理，我太弱了）但我们不急，不慌，不乱。想想DP，乱设一下，设\(f_i\)表示从(1,1)走到第i个不能走的点，且不经过其它不能走的点的方案数。推一下，设\(x_i,y_i\)为第i个不能通过的点（以\(x_i\)为第一关键字，\(y_i\)为第二关键字排好序后），我们可以用上文推到的东西先算出(1,1)这个点到总方案数，然后依照我们的定义：“不能经过其他无法通过的点”，所以要减去前\(i-1\)个点到此点的方案数（不合定义），就是\(f_i\)了,综上：
\[f_i=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1}*C_{x_i+y_i-x_j-x_j}^{x_i-x_j}\]
我们可以让终点成为不可通过的点，答案就是\(f_{n+1}\)了。
嗯嗯，讲完了。
\(O(n^2)\) 的时间复杂度，完美AC。\(n<=2000\)
那么，再综合解题步骤：
以\(x_i\)为第一关键字，\(y_i\)为第二关键字排好序。
提前预处理出组合数所需要的逆元（逆元可以自学，复习时我可能会写来巩固一下）。
把终点加入\(f\)中，计算\(f_i\)的值，答案就是\(f_{n+1}\)
附上完整代码，放心食用。(pascal的，重点在思路，语言无太大关系)
const p=trunc(1e9)+7;
type
node=record
x,y:int64;
end;
var
fac,inv:array [0..200005] of int64;
f:array [0..3005] of int64;
a,c:array [0..3005] of node;
n,m,i,j,k,maxn:longint;
procedure msort(l,r:longint);
var
i,j,k,mid:longint;
begin
mid:=(l+r)>>1;
if (l<mid) then msort(l,mid);
if (mid+1<r) then msort(mid+1,r);
i:=l;
j:=mid+1;
k:=l;
while (i<=mid)and(j<=r) do
begin
if (a[i].x<a[j].x)or(a[i].x=a[j].x)and(a[i].y<a[j].y) then
begin
c[k]:=a[i];
inc(i);
inc(k);
end
else begin
c[k]:=a[j];
inc(j);
inc(k);
end;
end;
while (i<=mid) do
begin
c[k]:=a[i];
inc(i);
inc(k);
end;
while (j<=r) do
begin
c[k]:=a[j];
inc(j);
inc(k);
end;
for i:=l to r do a[i]:=c[i];
end;
function qpow(x,y:int64):int64;
var
res:int64;
begin
res:=1;
while (y>0) do
begin
if (y and 1=1) then res:=res*x mod p;
x:=x*x mod p;
y:=y>>1;
end;
exit(res);
end;
procedure prepare;
var
i:longint;
begin
fac[0]:=1;
for i:=1 to maxn do fac[i]:=fac[i-1]*i mod p;
inv[maxn]:=qpow(fac[maxn],p-2);
for i:=maxn-1 downto 0 do inv[i]:=inv[i+1]*(i+1) mod p;
end;
function combination(n,m:int64):int64;
begin
if (n<m) then exit(0);
exit(fac[n]*inv[n-m] mod p*inv[m] mod p);
end;
begin
//assign(input,'path.in');reset(input);
//assign(output,'path.out');rewrite(output);
readln(n,m,k);
if (n<m) then maxn:=m<<1
else maxn:=n<<1;
for i:=1 to k do read(a[i].x,a[i].y);
k:=k+1;
a[k].x:=n;a[k].y:=m;
msort(1,k);
prepare;
for i:=1 to k do
begin
f[i]:=combination(a[i].x+a[i].y-2,a[i].x-1);
for j:=1 to i-1 do
f[i]:=(f[i]-f[j]*combination(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x) mod p+p) mod p;
end;
write(f[k]);
//close(input);close(output);
end.曲终，继续努力，备战CSP2019。