题目大意
小Y最近学得了最短路算法，一直想找个机会好好练习一下。话虽这么说，OJ上最短路的题目都被他刷光了。正巧他的好朋友小A正在研究一类奇怪的图，他也想凑上去求下它的最短路。
小A研究的图可以这么看：在一个二维平面上有任意点$(x,y)$（$0\le x\le N,0\le y\le M$,且$x,y$均为整数），且$(x,y)$向$(x-1,y)$（必须满足$1\le x$）和$(x,y-1)$（必须满足$1\le y$）连一条边权为$0$的双向边。
每个点都有一个非负点权，不妨设$(x,y)$的权值为$F[x][y]$，则有：
1.$x=0$或$y=0$：$F[x][y]=1$；
2.其他情况：$F[x][y]=F[x-1][y]+F[x][y-1]$。
现在，小Y想知道$(0,0)$到$(N,M)$的最短路，即使得经过的点的权值之和最小。为了炫耀自己学过最短路算法，他决定和你进行一场比赛，看谁的程序跑得快。然则小Y没有学过高精度算法，所以他希望输出答案时只输出答案模$1000000007$后的值。
题目分析
下文为了方便，将棋盘向右下移动一位，即从$(1,1)$开始编号。
首先我们画出棋盘：
其中第$i$行第$j$列为$C_{i-1+j-1}^{j-1}$。
通过打表或简单思考可得到贪心策略：
首先沿着$\max(n,m)$的方向行走到目标行/列，再沿着$\min(n,m)$的方向行走到达目标点。
故可以列出式子：
因为$\min(n,m)\le10^6$，故已经可做了。
但因为需要求逆元，因此效率略低。
优化：
根据杨辉三角的性质：
蓝色部分组合数相加等于下面的红色组合数减去上面的红色组合数。
根据杨辉三角的递推方式不难证明这一结论。
因为本题特殊的求和起点，因此需要减去的项为$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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1e9+7;
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
LL inv(LL x) {
return Quick_Pow(x,mod-2);
}
LL n,m;
int main() {
n=Get_Int()+1;
m=Get_Int()+1;
LL C=1,Min=min(n,m),Max=max(n,m),ans=Max-1;
for(int i=0; i<Min; i++) {
ans=(ans+C)%mod;
C=C*(Max-1+i+1)%mod*inv(i+1)%mod;
}
printf("%lld\n",ans);
return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const LL mod=1e9+7;
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
LL inv(LL x) {
return Quick_Pow(x,mod-2);
}
LL n,m;
int main() {
n=Get_Int()+1;
m=Get_Int()+1;
LL C=1,Min=min(n,m),Max=max(n,m),down=1,up=1;
for(LL i=1; i<Min; i++)down=down*i%mod;
for(LL i=Max+1; i<Max+Min; i++)up=up*i%mod;
printf("%lld\n",(up*inv(down)%mod+Max-1)%mod);
return 0;
}
