题目链接：Vijos - P1943
题目分析
这是 AHOI 普及组的题目，然而我并不会做= =弱到不行= =
首先，从 (x, 0) 到 (0, y) 的最短路，一定是只能向左走和向上走，那么用组合数算一下方案数是 C(x + y, x) ，记为 Solve(x, y), 其实就是将 y 次向上走分配到 x + 1 个横坐标上。
那么不考虑不能有交点的方案就是 Solve(x1, y1) * Solve(x2, y2) 。
然后题目要求两条路径不能有交点，那么我们就考虑容斥，用总的方案减去有交点的方案。
我们将两条相交的路径在最左端的交点处进行交换，即那个交点向左的部分，原先属于路径 1 的部分现在属于路径2，原先属于路径 2 的部分现在属于路径 1。
那么，我们就得到了一条从 (x1, 0) 到 (0, y2) 的路径和一条 (x2, 0) 到 (0, y1) 的路径，可以发现，这样的一对路径和原题中相交的一对路径是一一对应的。
那么我们的答案就是 Solve(x1, y1) * Solve(x2, y2) - Solve(x1, y2) * Solve(x2, y1) 。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; typedef long long LL; const int MaxN = 200000 + 5, Mod = 1000000007, MN = 200000; int x, y, xx, yy; LL Ans;
LL Fac[MaxN]; void Prepare()
{
Fac[0] = 1;
for (int i = 1; i <= MN; ++i)
Fac[i] = Fac[i - 1] * (LL)i % Mod;
} LL Pow(LL a, int b)
{
LL ret = 1, f = a;
while (b)
{
if (b & 1)
{
ret *= f;
ret %= Mod;
}
b >>= 1;
f *= f;
f %= Mod;
}
return ret;
} inline LL Inv(LL x)
{
return Pow(x, Mod - 2);
} LL C(int x, int y)
{
return Fac[x] * Inv(Fac[y]) % Mod * Inv(Fac[x - y]) % Mod;
} LL Solve(int x, int y)
{
return C(x + y, x);
} int main()
{
Prepare();
scanf("%d%d%d%d", &x, &xx, &y, &yy);
Ans = (Solve(x, y) * Solve(xx, yy) % Mod - Solve(x, yy) * Solve(xx, y) % Mod) % Mod;
Ans = (Ans + Mod) % Mod;
cout << Ans << endl;
return 0;
}