当前位置: 代码迷 >> 综合 >> 【HDU - 5698】瞬间移动(求组合数)
  详细解决方案

【HDU - 5698】瞬间移动(求组合数)

热度:28   发布时间:2023-12-06 19:38:03.0

有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第nn行第mm列的格子有几种方案,答案对10000000071000000007取模。 

Input

多组测试数据。 

两个整数n,m(2≤n,m≤100000)n,m(2≤n,m≤100000) 

Output

一个整数表示答案

Sample Input

4 5

Sample Output

10

思路:(参考博客)

求1e5范围内的组合数,二维数组的打表方式肯定是不行的。所以这里用了组合数的阶乘求法的公式,求出1e5以内数的阶乘,然后求逆元最后相乘。这道题目需要注意预处理的范围是2e5,因为最后是求n+m-4的,注意特判一下n=2或m=2的情况。

对于这道题目,可以先写出前几项找规律,最后能发现斜着是个杨辉三角。

ac代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#define mod (1000000007)
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll f[N];//阶乘会爆int 
void init(int n, int p) {f[1]=1; for(int i=2;i<n;i++){f[i]=f[i-1]*(ll)i%p;}
}
ll ex_gcd(ll a,ll b,ll &x,ll &y) {if (b == 0) {x=1,y=0;return a;}ll ret=ex_gcd(b,a%b,y,x);y-=a/b*x;return ret;
}
ll inv(ll a, ll m) { ///求除数a对m的逆元;ll d, x, y, t = (ll) m;d = ex_gcd(a,t,x,y);if (d == 1)return (x%t+t)%t;return -1;
}
ll qpow(ll a,ll b)
{ll t=1;while(b){if(b&1)t=t*a%mod;b>>=1;a=a*a%mod;}return t; 
}
int main()
{init(300000,mod);int n,m;while(~scanf("%d%d",&n,&m)){if(n==2||m==2) puts("1");elseprintf("%lld\n",1ll*f[n+m-4]*inv(f[n-2],mod)%mod*inv(f[m-2],mod)%mod); }return 0;
}