Saving Beans

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1666    Accepted Submission(s): 592

2
1 2 5
2 1 5

3
3
Hint
Hint

For sample 1, squirrels will put no more than 2 beans in one tree. Since trees are different, we can label them as 1, 2 … and so on. 
The 3 ways are: put no beans, put 1 bean in tree 1 and put 2 beans in tree 1. For sample 2, the 3 ways are:
 put no beans, put 1 bean in tree 1 and put 1 bean in tree 2.
 

一道很强悍的数论题目,推都推不出来,但是好在,有别人的思路,明天再推推,看看能不能推出来,

但是有很多的知识点,比如说,费马小定理,比如说,lucas还比如说求c(n,m)

这些都是很基础的算法,但是自己以前都不知道,这一道题目都让我全部用到了,自己果然是菜鸟中的菜鸟,不过学到了知识,自己还是很开心的.

拿来别人的解题报告看看.

然后贴出自己的代码

题目相当于求n个数的和不超过m的方案数。

如果和恰好等于m，那么就等价于方程x1+x2+...+xn = m的解的个数，利用插板法可以得到方案数为：

(m+1)*(m+2)...(m+n-1)  = C(m+n-1,n-1) = C(m+n-1,m)

现在就需要求不大于m的，相当于对i = 0,1...,m对C(n+i-1,i)求和，根据公式C(n,k) = C(n-1,k)+C(n-1,k-1)得

C(n-1,0)+C(n,1)+...+C(n+m-1,m)

= C(n,0)+C(n,1)+C(n+1,2)+...+C(n+m-1,m)

= C(n+m,m)

现在就是要求C(n+m,m) % p,其中p是素数。

然后利用Lucas定理的模板就可以轻松的求得C(n+m,m) % p的值

下面简单介绍一下Lucas定理：

Lucas定理是用来求 C(n,m) mod p的值,p是素数（从n取m组合，模上p）。
描述为:
Lucas(n,m,p)=C(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;

简单的理解就是：

以求解n! % p 为例，把n分段，每p个一段，每一段求得结果是一样的。但是需要单独处理每一段的末尾p,2p,...,把p提取出来，会发现剩下的数正好又是(n/p)! ，相当于

划归了一个子问题，这样递归求解即可。

这个是单独处理n！的情况，当然C(n,m)就是n！/(m! *（ｎ－ｍ）！），每一个阶乘都用上面的方法处理的话，就是Lucas定理了

Lucas最大的数据处理能力是p在10^5左右。

而C(a,b) =a! / ( b! * (a-b)! ) mod p

其实就是求 ( a! / (a-b)!)  * ( b! )^(p-2) mod p

  (上面这一步变换是根据费马小定理：假如p是质数，且a,p互质，那么a的（p-1）次方除以p的余数恒为1,

那么a和a^(p-2)互为乘法逆元，则（b / a) = (b * a^(p-2) ) mod p)

用下面的Lucas定理程序实现就能得出结果，实现过程中要注意乘法时的强制转换

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

using namespace std;

int N, M, P;

int fac[100011];

void factorial()
{
	fac[0] = 1;
	for (int i = 1; i <= P; i++)
	{
		fac[i] = (long long int)fac[i - 1] * i % P;
	}

} 

int quick_pow(int a, int n)
{
	int ans = 1;

	while (n)
	{
		if (n & 1)
		{
			ans = (long long int)ans * a % P;
		}
		a = (long long int) a * a % P;
		n >>= 1;
	}
	return ans;
}

		

int C(int n, int m)
{
	if (n < m)
	{
		return 0;
	}
	return (long long int)fac[n] * (quick_pow((long long int)fac[m] * fac[n - m] % P, P - 2)) % P;
}
		
	

int lucas(long long int n, long long int m)
{
	if (m == 0)
	{
		return 1;
	}
	return (long long int)C(n % P, m % P) * lucas(n / P, m / P) % P;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d%d", &N, &M, &P);
		factorial();
		int ans = lucas(N + M, M);
		printf("%d\n", ans);
	}
//	system("pause");
	return 0;
}