描述
小雪与小可可吵架了，他们决定以后互相再也不理对方了。尤其是，他们希望以后上学的路上不会再相遇。
我们将他们所在城市的道路网视作无限大的正交网格图，每一个整数点 (x,y) 对应了一个路口，相邻两个整数点之间有一条平行于 x 轴或平行于 y 轴的道路，其道路长度为 1。已经知道小雪家住在 (x_1,0) 处的路口附近，小可可的家住在 (x_2,0) 处的路口附近。另外我们还知道，小雪的学校在 (0,y_1) 处的路口附近，小可可的学校在 (0,y_2) 处的路口附近。其中保证 x_1 < x_2 且 y_1 < y_2。
因为上学不能迟到，所以小雪和小可可总是希望可以走最短路径去上学。同时为了避免见面，希望他们所选择的路线可以没有交点。
格式
输入格式
输入的第一行输入四个正整数，依次为 x_1, x_2, y_1, y_2，满足 x_1 < x_2 且 y_1 < y_2。
输出格式
在输出中，输出一个非负整数，表示可行方案的总数 ans 关于常数 10^9+7 取余后的值。
限制
对于30%的数据，0 < x_1,x_2,y_1,y_2<=500。
对于70%的数据，0 < x_1,x_2,y_1,y_2<=3000。
对于100%的数据，0 < x_1,x_2,y_1,y_2<=100000。
对于70%的数据，0 < x_1,x_2,y_1,y_2<=3000。
对于100%的数据，0 < x_1,x_2,y_1,y_2<=100000。
今天中午某人屁颠屁颠跑到我班跟我说这题容斥原理blah blah blah，我当时就想= =我们学校终于有救了，又出一奇才！中午他把程序打好，确实能过样例。。但按那种做法= =runtime error 0分。。
这题实在没辙了，然后我就去找题解= =找到了一思路满分没贴程序的题解：“
本题考虑用容斥的思想。
对于任意的最短路径path1和path2，若相交，则存在一个交点x。
在x处交换两个路径，得到新的路径path3和path4，满足path3从(x1,0)到(0,y2)而path4从(x2,0)到(0,y1)。
综上所述，整个问题的最后结果＝“(x1,0)到(0,y1)的方案数”ד(x2,0)到(0,y2)的方案数”－“(x1,0)到(0,y2)的方案数”ד(x2,0)到(0,y1)的方案数”。
而每一部分可以分别用组合数来表示。时间复杂度O(nlogn+n^{1.5})。
本题还可以利用动态规划的方法，用三维的状态F[i][j][k]来表示两人同时走到y=i是所在横坐标的位置，其转移是O(1)的，总时间复杂度为O(n^3)，
这样可以得到30分的部分分。
如果利用容斥的思想，可以加速到O(n^2)，得到70分。
”
简直了= =我明白他怎么“想”到了= =
然后在加上初赛时学的找路径的万能大法，他的程序应当是这样的：
program school;
var
x1,x2,y1,y2:longint;
function work(x,y:longint):longint;
var
d:array[0..2000,0..2000]of longint;
i,j:longint;
begin
fillchar(d,sizeof(d),0);
for i:=0 to x do
d[i][0]:=1;
for i:=0 to y do
d[0][i]:=1;
d[0][0]:=0;
for i:=1 to x do
for j:=1 to y do
d[i][j]:=(d[i-1][j]+d[i][j-1])mod 1000000007;
exit(d[x][y] mod 1000000007);
end;
begin
readln(x1,x2,y1,y2);
writeln((work(x1,y1)*work(x2,y2)-work(x1,y2)*work(x2,y1))mod(1000000007));
end.
这里就又涉及到了一个问题“找路径”
我们可以这样理解，对于M*N的方格，从(0,0)到(M,N)，就是在长为（M+N）的路径中选取M种与x轴平行，或N种与y轴平行的路径。
可以用组合数来表示 C(m+n,m)或C(m+n,n)，其实这里我们也能得到一个结论：C(m+n,m)=C(m+n,n)
这样看来，主程序只有两句话，但要定义一个函数COMB(M,N)
如何解决呢？
以后再说
评论 (0)
