3.上学路上
本题考虑用容斥的思想。对于任意的最短路径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分。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
#define mod 1000000007
using namespace std;
int x1,x2,y1,y2,fac[200005];

void pre(){
    fac[1]=1;
    for(int i=2;i<=y2+x2+10;i++)
    fac[i]=1ll*fac[i-1]*i%mod;
}

int mul(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;b>>=1;
    }
    return ans;
}

int calc(int x,int y){
    int ans=1ll*fac[x+y]*mul(fac[x],mod-2)%mod;
    ans=1ll*ans*mul(fac[y],mod-2)%mod;
    return ans;
}

int main(){
    scanf("%d%d%d%d",&x1,&x2,&y1,&y2);pre();
    int t1=1ll*calc(x1,y1)*calc(x2,y2)%mod;
    int t2=1ll*calc(x1,y2)*calc(x2,y1)%mod;
    printf("%d",(t1-t2+mod)%mod);
    return 0;
}

#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
const LL M=1000000007;
LL x1, x2, y1, y2;
LL MOD (LL a, LL m) {
    while(a>m) a-=m;
    while(a<0) a+=m;
    return a;
}
LL QUICKPOW (LL a, LL k, LL m) {
    LL ans=1;
    while(k>0) {
        if (k&1) ans=ans*a%m;
        a=a*a%m;
        k>>=1;
    }
    return ans%m;
}
LL IE (LL a, LL m) {
    return QUICKPOW(a, m-2, m);
}
LL C(LL a, LL b, LL m) {
    LL x=1, y=1;
    for(int i=b-a+1; i<=b; i++) x=x*i%m;
    for(int i=1; i<=a; i++) y=y*i%m;
    LL e=IE(y, m), ans;
    ans=x*e%m;
    return ans;
}
int main () {
    
    ios::sync_with_stdio(false);
    cin >> x1 >> x2 >> y1 >> y2;
    LL ans=MOD(C(x1, x1+y1, M)*C(x2, x2+y2, M)-C(x1, x1+y2, M)*C(x2, x2+y1, M), M);
    cout << ans;
    return 0;
    
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <stdlib.h>
#include <vector>
#include <map>
#include <fstream>
#include <string.h>

#define ll long long
#define clr(x) memset(x,0,sizeof(x))
#define clr2(x) memset(x,INF,sizeof(x))
#define clr3(x) memset(x,-INF,sizeof(x))
#define clr4(x) memset(x,-1,sizoef(x))
#define MAXN 200010
#define MAXM 200010

using namespace std;

const ll mod=1e9+7;
ll fac[MAXN];
ll quick_mod(ll a,ll b,ll m)
{
ll res=1;
while (b)
{
if (b&1)
{
res=(res*a)%m;
b--;
}
b/=2;
a=a*a % m;
}
return res;
}

void init()
{
fac[0]=1;
for (int i=1;i<=MAXN;i++)
fac[i]=fac[i-1]*i % mod;
}

ll C(ll a,ll b)
{
return fac[a] * quick_mod(fac[b],mod-2,mod) % mod * quick_mod(fac[a-b],mod-2,mod) % mod ;
}
void solve()
{
ll x1,x2,y1,y2;

cin>>x1>>x2>>y1>>y2;
init();
ll ans= C(x1+y1,x1) * C(x2+y2,x2) % mod - C(x1+y2,x1) * C(x2+y1,x2) % mod;
ans = ( ans + mod ) % mod;
cout<<ans<<endl;

}
int main()
{

solve();
return 0;
}

二阶行列式的解

模板题. 题解见上方出题人doc.我就放个代码。

编译成功

测试数据 #0: Accepted, time = 62 ms, mem = 1812 KiB, score = 5
测试数据 #1: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #2: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #3: Accepted, time = 46 ms, mem = 1812 KiB, score = 5
测试数据 #4: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #5: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #6: Accepted, time = 46 ms, mem = 1820 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #9: Accepted, time = 46 ms, mem = 1820 KiB, score = 5
测试数据 #10: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #11: Accepted, time = 62 ms, mem = 1812 KiB, score = 5
测试数据 #12: Accepted, time = 62 ms, mem = 1816 KiB, score = 5
测试数据 #13: Accepted, time = 46 ms, mem = 1820 KiB, score = 5
测试数据 #14: Accepted, time = 62 ms, mem = 1816 KiB, score = 5
测试数据 #15: Accepted, time = 62 ms, mem = 1812 KiB, score = 5
测试数据 #16: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #17: Accepted, time = 62 ms, mem = 1820 KiB, score = 5
测试数据 #18: Accepted, time = 62 ms, mem = 1812 KiB, score = 5
测试数据 #19: Accepted, time = 62 ms, mem = 1812 KiB, score = 5

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MOD = 1000000007;
const int maxn = 200009;

int x0, x1, y0, y1;
int fac[maxn], inv[maxn];

void Gcd(int a, int b, int &x, int &y) {
if(!b) {
x = 1, y = 0;
} else {
Gcd(b, a % b, y, x);
y -= x * (a / b);
}
}

int Inv(int v) {
int x, y;
Gcd(v, MOD, x, y);
return (x + MOD) % MOD;
}

void Init() {
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for(int i = 2; i < maxn; i++)
inv[i] = Inv(fac[i] = ll(i) * fac[i - 1] % MOD);
}

int C(int n, int m) {
return ll(fac[n]) * inv[m] % MOD * inv[n - m] % MOD;
}

int main() {

Init();
scanf("%d%d%d%d", &x0, &x1, &y0, &y1);
printf("%d\n", (int) ((((ll) C(x0 + y0, x0) * C(x1 + y1, x1) % MOD - (ll) C(x0 + y1, x0) * C(x1 + y0, x1) % MOD) % MOD + MOD) % MOD));

return 0;
}