学步园

为什么我要再把这道题目拿出来，我是真的想提醒一下自己。

做算法的题目和数学题目其实是一样的，没有完整的思路，没有切实的方法，

没有及其的小心，细心你是做不出来题目的。

你必须要当心，敲代码的时候时刻看着上面自己敲得是否合适，不合适或者自己现在不知道

合适不合适，或者有一定的几率错的地方一定要标注下来。

下面的代码，自己这几天刚刚实现过，但是现在写起来还是写错了好多次。原因就是自己没有注意int*int是极有可能

出现long long的，而自己却没有注意。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

int N, M, P;

int quick_pow(int a, int n)
{
	int ans = 1;
	while (n)
	{
		if (n & 1)
		{
			ans = (long long int)ans * a % P;//这里的long long int也是必须的 
		}
		a = (long long int)a * a % P; // 也是必须的. 
		n >>= 1;
	}
	return ans;
}

int C(int n, int m)
{
	if (n < m)
	{
		return 0;
	}
	int ans = 1;
	for (int i = 1; i <= m; i++)
	{
		int t = (n - m + i) % P;
		int b = i % P;
		int temp = (long long int)t * quick_pow(b, P - 2) % P; //这里的long long int也是必须的; 
		ans = (long long int)ans * temp % P;//这里的long long int 也是必须的 
	}
	return ans;
}

int lucas(int n, int m)
{
	if (m == 0)
	{
		return 1;
	}
	return (long long int)C(n % P, m % P) * lucas(n / P, m / P) % P; //所有的这些(long long int)都是要加上的,你不能肯定所有的数据都在int 
}

int main()
{
	while (scanf("%d%d%d", &N, &M, &P) != EOF)
	{
		int t = N - M + 1;
		if (t < M)
		{
			printf("0\n");
			continue;
		}
		if (t - M < M)
		{
			M = t - M;
		}
		int ans = lucas(t, M);
		printf("%d\n", ans);
	}
//	system("pause");
	return 0;
}

再贴出来一个用extgcd求逆元的代码,代码运行要快的多了,180ms而上面的590

以后还是要尽量用extgcd,,注意求出来之后要 x要处理一下,因为有可能出现的数是负数,所以

x = (x % p +　ｐ)％ｐ

贴出代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

/*
 *一般一出现素数作为MOD的题目,基本上就是lucas了;
 *而这类题目的难点也就在推导出排列组合公式，后面的lucas，快速幂什么的
 *都是浮云！还是要做个排列组合的专题的。
 *时间才用了180ms,比quick_pow要快很多,以后尽量还是要用extgcd来求逆元 
 */ 

int N, M, P;

/*
int quick_pow(int a, int n)
{
	int ans = 1;
	while (n)
	{
		if (n & 1)
		{
			ans = (long long int)ans * a % P;//这里的long long int也是必须的 
		}
		a = (long long int)a * a % P; // 也是必须的. 
		n >>= 1;
	}
	return ans;
}
*/
int extgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	int d = extgcd(b, a % b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
	return d;
}

int C(int n, int m)
{
	if (n < m)
	{
		return 0;
	}
	int ans = 1;
	for (int i = 1; i <= m; i++)
	{
		int t = (n - m + i) % P;
		int b = i % P;
//		int temp = (long long int)t * quick_pow(b, P - 2) % P; //这里的long long int也是必须的; 
		int x, y;
		int d = extgcd(b, P, x, y);
		x = (x % P + P) % P;//为什么不可以呀???晕死了就!!! 
		int temp = (long long int)t * x % P; //这里也要mod P, 
		ans = (long long int)ans * temp % P;//这里的long long int 也是必须的 
	}
	return ans;
}

int lucas(int n, int m)
{
	if (m == 0)
	{
		return 1;
	}
	return (long long int)C(n % P, m % P) * lucas(n / P, m / P) % P; //所有的这些(long long int)都是要加上的,你不能肯定所有的数据都在int 
}

int main()
{
	while (scanf("%d%d%d", &N, &M, &P) != EOF)
	{
		int t = N - M + 1;
		if (t < M)
		{
			printf("0\n");
			continue;
		}
		if (t - M < M)
		{
			M = t - M;
		}
		int ans = lucas(t, M);
		printf("%d\n", ans);
	}
//	system("pause");
	return 0;
}