51nod 1627 瞬間移動(dòng) 組合數(shù)取模

2019-11-14 08:51:35

字體：大中小

供稿：網(wǎng)友

關(guān)于組合數(shù)取模和逆元的知識(shí)的參考 http://blog.csdn.net/acdreamers/article/details/8037918 http://blog.csdn.net/acdreamers/article/details/8220787#comments 題目：有一個(gè)無限大的矩形，初始時(shí)你在左上角（即第一行第一列），每次你都可以選擇一個(gè)右下方格子，并瞬移過去（如從下圖中的紅色格子能直接瞬移到藍(lán)色格子），求到第n行第m列的格子有幾種方案，答案對(duì)1000000007取模。這里寫圖片描述 Input 單組測(cè)試數(shù)據(jù)。兩個(gè)整數(shù)n,m（2<=n,m<=100000） Output 一個(gè)整數(shù)表示答案。 Input示例 4 5 Output示例 10 可通過打表或者其他理解得出答案為C(m+n-4，m-2)或C(m+n-4，n-2)//可優(yōu)化的地方

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;typedef long long ll;#define mem(s,n) memset(s,n,sizeof(s))int p = 1000000007;ll quick_mod(ll a,ll b)//a^b%p 快速冪{ ll ans = 1; a %= p; while(b) { if(b & 1) { ans = ans * a % p; b--; } b >>= 1; a = a * a % p; } return ans; }ll C(ll n,ll m)//nCm %p{ if(n < m) return 0; ll ans = 1; for(ll i=1;i<=m;i++) { ll a = (n - m + i) % p; ll b = i % p; ans = ans *(a * quick_mod(b,p-2) % p) % p;//逆元的知識(shí) } return ans;}ll Lucas(ll n,ll m)//Lucas定理{ if(m == 0) return 1; return C(n % p,m % p) * Lucas(n / p,m / p) % p;}int main(int argc, char *argv[]){ ll m,n,a,b; scanf("%lld%lld",&m,&n); b=m+n-4; a=min(m-2,n-2); 對(duì)于正整數(shù) a 和 p,若 ax≡1 mod p, 則稱a關(guān)于模f的乘法逆元為x。也可表示為ax≡1(mod p)。逆元一般用擴(kuò)展歐幾里得算法來求得，如果為素?cái)?shù)，那么還可以根據(jù)費(fèi)馬小定理得到逆元為 ap?2≡1a $a^{p-2}≡/frac{1}{a}$ (mod p) 實(shí)際應(yīng)用主要用于處理除法取模如組合數(shù)

這里寫圖片描述和且p為素?cái)?shù) Lucas定理：則有利用逆元計(jì)算即可