瞬間移動(dòng)

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1422????Accepted Submission(s): 684

Problem Description 有一個(gè)無(wú)限大的矩形，初始時(shí)你在左上角（即第一行第一列），每次你都可以選擇一個(gè)右下方格子，并瞬移過(guò)去（如從下圖中的紅色格子能直接瞬移到藍(lán)色格子），求到第n 行第m 列的格子有幾種方案，答案對(duì)1000000007 取模。

?

?

Input 多組測(cè)試數(shù)據(jù)。

兩個(gè)整數(shù)n,m(2≤n,m≤100000)
?

?

Output 一個(gè)整數(shù)表示答案 ?

?

Sample Input 4 5 ?

?

Sample Output 10 ?

?

Source 2016"百度之星" - 初賽（Astar Round2B）? x和y分開(kāi)考慮，在（1,1）到（n，m）之間可以選擇走i步。就需要選i步對(duì)應(yīng)的行C（n-2，i）及i步對(duì)應(yīng)的列C（m-2，i）。相乘起來(lái)。 假設(shè)m<=n
#include<iostream> #include<cstdio> #include<cstring>#define N 200001 #define M 1000000007 #define ll long longusing namespace std; ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1}; int n,m;ll C(ll a,ll b) {return fac[a]*inv[b]%M*inv[a-b]%M; }int main() {for(int i=2;i<N;i++){fac[i]=fac[i-1]*i%M;f[i]=(M-M/i)*f[M%i]%M;inv[i]=inv[i-1]*f[i]%M;}while(~scanf("%d%d",&n,&m)) printf("%lld\n",C(m+n-4,m-2));return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/L-Memory/p/7424092.html

總結(jié)

以上是生活随笔為你收集整理的hdu5698瞬间移动(组合数，逆元)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。