A Path Plan

好久没有写博客,放假一直在划水,最近每次打 $codeforces$ 都做不出千人题,👎

C - A Path Plan

题意:
$A$ 从 $(0,y_1)$ 前往 $(x_1,0)$
$B$ 从 $(0,y_2)$ 前往 $(x_2,0)$
只能走 $R$ 和 $D$

问有多少种不相交的走法 $(x_2 > x_1,y_2 > y_1)$

思路

$ans$ = 所有走法 - 相交的走法

很显然,所有的走法是 $C_{x_1+y_1}^{x_1} \cdot C_{x_2+y_2}^{x_2}$

这里有一个很妙的思路:

交换 $(x_1,0)$ 和 $(x_2,0)$

此时所有的走法必定相交,这些路其实就是相交的走法,把后半段路互换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

int T,x1,y1,x2,y2;

int qmod(int a,int b){
int res = 1;
while(b){
if(b & 1){
res *= a;
res %= mod;
}
a = (a * a) % mod;
b >>= 1;
}
return (res+mod) % mod;
}


int C(int m,int n){//C_m ^ n
int a = 1;
int b = 1;
for(int i = 1;i <= n;i++){
a = a*(m - i + 1) % mod;
b = b * i % mod;
}
return a * qmod(b,mod-2) % mod;
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld%lld",&x1,&x2,&y1,&y2);
printf("%lld\n",((C(x1+y1,x1) * C(x2+y2,x2) % mod) - (C(x1+y2,x1) * C(x2 + y1,x2) % mod) + mod) % mod);
}
}