Walk

NC206842. Walk

描述

多多喜欢行走，有一天老师问他一个问题：在一个方格点阵中，左上角点的坐标为(1, 1)，行坐标从上到下依次递增，列坐标从左到右依次递增，每次行走可以向上、下、左、右移动一格。现在要从(1, 1)点走到(N, M)点，在行走步数最少的情况下，有多少种行走方法？(答案可能过大，请对答案取模1000000007)

输入描述

第一行输入一个正整数 T，代表询问次数 (1 ≤ T ≤ 100000)
接下来 T 行，每行输入两个正整数 N，M (1 ≤ N ≤ 10⁶，1 ≤ M ≤ 10⁶)

输出描述

对于每次询问，输出一个正整数，代表在行走步数最少的情况下，从(1, 1)点走到(N, M)点的方法总数 (答案可能过大，请对答案取模1000000007)

示例1

输入:

1
2 2

输出:

说明:

(1, 1) (1, 2)

(2, 1) (2, 2)

在步数最少的情况下，从(1, 1)走到(2, 2)的方法有2种：

第一种：(1, 1) -> (1, 2) -> (2, 2)

第二种：(1, 1) -> (2, 1) -> (2, 2)

示例2

输入:

1
2 3

输出:

说明:

(1, 1) (1, 2) (1, 3)

(2, 1) (2, 2) (2, 3)

在步数最少的情况下，从(1, 1)走到(2, 3)的方法有3种：

第一种：(1, 1) -> (1, 2) -> (1, 3) -> (2, 3)

第二种：(1, 1) -> (1, 2) -> (2, 2) -> (2, 3)

第三种：(1, 1) -> (2, 1) -> (2, 2) -> (2, 3)

示例3

输入:

1
5 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 221ms, 内存消耗: 18520K, 提交时间: 2020-06-25 00:12:51

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=2e6+10;
ll f[maxn];
ll fpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		b/=2;a=(a*a)%mod;
	}
	return ans%mod;
}
void init(){
	f[0]=1;f[1]=1;
	for(int i=2;i<maxn;i++) f[i]=(f[i-1]*i)%mod;
}

int main()
{
	init();
	int t;
	cin>>t;
	while(t--){
		ll n,m;
		scanf("%lld%lld",&n,&m);
		cout<<(f[n+m-2]*fpow((f[n-1]*f[m-1])%mod,mod-2))%mod<<endl;
	}
	return 0;	
}

C++11(clang++ 3.9) 解法, 执行用时: 284ms, 内存消耗: 17016K, 提交时间: 2020-06-14 14:25:46

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int mod=1000000007;
ll n,m,fac[maxn*2],x,y;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)	x=1,y=0;
	else	exgcd(b,a%b,y,x),y-=a/b*x;
}
int main()
{
	fac[0]=1;
	for(ll i=1;i<=2000000;i++)	fac[i]=fac[i-1]*i%mod;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		ll temp=fac[n-1]*fac[m-1];
		exgcd(temp,mod,x,y);
		x=(x%mod+mod)%mod;
		cout<<x*fac[n+m-2]%mod<<endl;
	}
}