频道栏目
首页 > 考试 > 其他 > 正文

编程开发瞬间移动问题解析

2018-05-05 10:54:07         来源:qq_41510496的博客  
收藏   我要投稿

编程开发瞬间移动问题解析。有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第n行第m列的格子有几种方案,答案对1000000007取模。

\
Input
单组测试数据。
两个整数n,m(2<=n,m<=100000)
Output
一个整数表示答案。
Input示例
45
Output示例
10

题解:可以发现其实答案就是个逆时针旋转了45度的杨辉三角。

我们设f[i][j]为答案,sum[i][j]为以i,j为右下角的答案总和。

那么f[i][j]=sum[i-1][j-1],f[i-1][j]+f[i][j-1]=sum[i-2][j-1]+sum[i-1][j-2],此时如果不算重复部分,那么f[i][j]还差f[i-1][j-1]这一部分,即sum[i-2][j-2]。因为sum[i-2][j-2]重复计算了两次,又因为sum[i-2][j-2]为f[i-1][j-1]的答案,所以减掉这重复部分之后再加上sum[i-2][j-2]恰好等于sum[i-1][j-1],即为f[i][j],所以f[i][j]为f[i-1][j]+f[i][j-1]。

这不就是杨辉三角吗QAQ

又因杨辉三角跟组合数有关,所以我们直接跑一波组合数就行了。

下面是我在KFC的手稿:

\

代码:

#include
using namespace std;
void exgcd(long long n,long long m,long long &x,long long &y){
	if(!m){
		x=1;y=0;
		return;
	}
	exgcd(m,n%m,x,y);
	long long t=x;
	x=y;y=t-n/m*y;
}
long long niyuan(long long x1){
	long long x=0,y=0;
	exgcd(x1,1000000007,x,y);
	return (x%1000000007+1000000007)%1000000007;
}
int main(){
	long long n,m,i,ans,n1,m1;
	scanf("%lld%lld",&n,&m);
	if(n==1&&m==1){
		printf("1");
		return 1;
	}
	if(n==1||m==1){
		printf("0");
		return 1;
	}
	n1=n+m-4;m1=m-2;
	ans=1;
	for(i=n1;i>=n1-m1+1;i--)ans=(ans*i)%1000000007;
	for(i=2;i<=m1;i++){
		//printf("%lld\n",niyuan(i));
	ans=(ans*niyuan(i))%1000000007;
}
	printf("%lld",ans);
}
上一篇:编程开发害死人不偿命的(3n+1)猜想
下一篇:The Cow Doctor【bitset+枚举】
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站