首页 > 代码库 > 【codevs1515】 跳

【codevs1515】 跳

2024-08-29 04:29:36   216人阅读

http://codevs.cn/problem/1515/ (题目链接)

题意

　　给出一个棋盘，规定走到(x,y)的花费C(x,y)=C(x-1,y)+C(x,y-1)，x=0或y=0时C(x,y)=1。求从(0,0)走到(n,m)的路径上的花费和的最小值。

Solution

　　画画图很容易就会发现是个杨辉三角，我们假设${n<=m}$于是问题就转化为了求解：

$${\sum^{n}_{i=0}{C^i_{m+i}}}$$

　　然后就不会了，翻了题解，没想到还有这种公式。。

$${\sum^{n}_{i=0}{C^i_{m+i}}=C^n_{n+m+1}}$$

　　来证明一下。对于一个组合${C^n_m}$我们可以这样来表示：格点图上从(0,0)到(n-m,m)的路径条数。（不好画图，尴尬→_→）

　　那么${\sum^{n}_{i=0}{C^i_{m+i}}}$就可以分别表示为：从(0,0)到(m,0)的路径条数；从(0,0)到(m,1)的路径条数；从(0,0)到(m,2)的路径条数······从(0,0)到(m,n)的路径条数。

　　而${C^n_{n+m+1}}$就可以表示为从(0,0)到(m+1,n)的路径条数。这与前者有什么关系呢？很简单，自己画个图就明白了。

　　于是我们用Lucas定理求解组合数取模。（然而这数据范围是什么鬼）

代码

// codevs1515#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL power(LL a,LL b) {	LL res=1;	while (b) {		if (b&1) res=res*a%MOD;		b>>=1;a=a*a%MOD;	}	return res;}LL C(LL n,LL m) {	LL s1=1,s2=1;	for (int i=n-m+1;i<=n;i++) s1=s1*i%MOD;	for (int i=1;i<=m;i++) s2=s2*i%MOD;	return s1*power(s2,MOD-2)%MOD;}LL Lucas(LL n,LL m) {	if (m==0) return 1;	return C(n%MOD,m%MOD)*Lucas(n/MOD,m/MOD)%MOD;}int main() {	LL n,m;	scanf("%lld%lld",&n,&m);	printf("%lld",(max(n,m)+Lucas(n+m+1,min(n,m)))%MOD);	return 0;}

　　

【codevs1515】 跳


联系
我们