隐藏
「bzoj2886」最短路 - 组合数学+找规律 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj2886」最短路 - 组合数学+找规律

题目大意

    小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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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;
}

姥爷们赏瓶冰阔落吧~