組合數取模

刷了幾道組合數取模的題，模闆都是一樣的  Lucas定理

關于Lucas定理   https://blog.csdn.net/cai_haiq/article/details/75954298    這個部落格講得很好

下面是模闆

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int INF = 0x3f3f3f3f;
const ll p = 1e9+7;
ll nn,mm,kk;

ll qpow(ll n, ll m, ll p)
{
	ll res=1;
	while(m)
	{
		if(m%2!=0)
		{
			res*=n;
			res%=p;
		}
		n*=n;
		n%=p;
		m/=2;
	}
	return res;
}

ll C(ll n,ll m,ll p)
{
	if(m>n) return 0;
	ll a=1,b=1;
	while(m)
	{
		a*=n;
		a%=p;
		n--; 
		b*=m;
		m--;
		b%=p;
	}
	return a*qpow(b,p-2,p)%p;
}

ll Lucas(ll n,ll m,ll p)
{
	if(m==0)
		return 1;
	return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
	
	
}

int main()
{
	std::ios::sync_with_stdio(false);
	int t;
	while(cin>>nn>>mm)
	{
		
		if(nn<mm)swap(nn,mm);

			ll b=Lucas(nn+mm-4,nn-2,p)%p;
			cout<<b<<endl;

		
	} 

	return 0;
} 
           

例題

1、hdu3037   http://acm.hdu.edu.cn/showproblem.php?pid=3037

公式：

n棵樹儲存m個豆子

問題轉化為

假設n+m棵樹，每棵樹最多儲存一個豆子

這樣就是上面那個公式

2、hdu5894    http://acm.hdu.edu.cn/showproblem.php?pid=5894

公式

證明 

https://blog.csdn.net/hjt_fathomless/article/details/52588392

3、hdu6114  http://acm.hdu.edu.cn/showproblem.php?pid=6114

這個比較簡單

公式

從n行裡面選出m行，按照1-m放進去就行

hdu5698  http://acm.hdu.edu.cn/showproblem.php?pid=5698

公式

題解

https://blog.csdn.net/qwb492859377/article/details/51478117

雖然看了題解我還是不了解  但是感覺和hdu3037有點像