程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3557 How Many Sets II lucas 定理

ZOJ 3557 How Many Sets II lucas 定理

編輯:C++入門知識

ZOJ 3557 How Many Sets II lucas 定理


插空法 大組合數取余

#include 
#include 
using namespace std;
typedef long long LL;

//求整數x和y,使得ax+by=d, 且|x|+|y|最小。其中d=gcd(a,b) 
void gcd(LL a, LL b, LL& d, LL& x, LL& y)
{
	if(!b)
	{
		d = a;
		x = 1;
		y = 0;
	}
	else
	{
		gcd(b, a%b, d, y, x);
		y -= x * (a/b);
	}
}
//計算模n下a的逆。如果不存在逆, 返回-1 
LL inv(LL a, LL n)
{
	LL d, x, y;
	gcd(a, n, d, x, y);
	return d == 1 ? (x+n)%n : -1;
}
LL cm(LL n, LL m, LL p)
{
	LL ans1 = 1, ans2 = 1;
	while(m)
	{
		ans1 = ans1*n%p;
		ans2 = ans2*m%p;
		n--;
		m--; 
	}
	return ans1*inv(ans2, p)%p;
}
LL lucas(LL n, LL m, LL p)
{
	if(m == 0)
		return 1;
	return lucas(n/p, m/p, p)*cm(n%p, m%p, p)%p;
}
int main()
{
	LL n, m, p;
	while(scanf("%lld %lld %lld", &n, &m, &p) != EOF)
	{		
		printf("%lld\n", lucas(n-2*m+1+m, m, p));
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved