【日常学习】【组合数取模Lucas定理】HDU3037 Saving Beans题解

Myth丶恋晨 2022-08-01 03:05 167阅读 0赞

【提前声明：此题没有通过！WA！有待进一步研究修改。放在这里只是起一个例子的作用，其实这道题鄙人并没有真正掌握= =】、

【本文努力抄袭模仿了小花妹妹的博文0[戳我][Link 1]0）】

*  题目大意：共T个测试点，每个测试点中，给定n、m，求将不超过m个种子放入n个坑的方案总数，最后答案对质数p取模。（一共m个，每个坑放多少无所谓，最后没放完m个也无所谓）
 *  数据范围：1 <= n, m <= 1000000000, 1 < p < 100000。
 *  思路：原题意即求方程x1+…+xn=m解的个数，因为中间的每一项均可为0，故两面同时将加上n，转换成为x1+…+xn+n=m+n，即x1’+…+xn’=m+n，其中每一项至少为1，则由隔板法可知，解的个数为C(n+m-1,m),这只是恰好为m个的方案数，总数为ans=C(n-1,0)+C(n,1)+…+C(n+m-1,m)=C(n+m,m)。（注意，这里组合数的意思表示为：n+m选m个）
 *  知识储备：
    
     *  (A \* B) mod C = (A mod C) \* (B mod C) mod C
     *  Lucas定理：记Lucas(n,m,p)=C(n,m) mod p，则Lucas(n,m,p)=C(n%p,m%p)\*Lucas(n/p,m/p,p)。
     *  乘法逆元：假如p是质数，且a、p互质，那么a的（p-1）次方除以p的余数恒为1,那么a和a^(p-2)互为乘法逆元，则(b / a) = (b \* a^(p-2) ) mod p。
 *  注意：中途必须强制转换类型，否则出错。【但没有人知道为什么而且最后还是挂了】

鄙人代码：

//HDU3037 Saving Beans Lucas¶¨Àí×éºÏÊýÈ¡Ä£ 
    //copyright by ametake
    
    #include<iostream>
    using namespace std;
    
    typedef long long ll;
    
    ll t,n,m,p;
    
    ll multi(ll a,ll b)
    {
    	ll ans=1;
    	while (b>0)
    	{
    		if (b & 1 == 1) ans=((ll)ans*(ll)a)%p;
    		a =( (ll)a * (ll)a ) % p;
    		b =(ll)(b << 1); 
    	}
    	return ans;
    }
    
    ll c(ll n,ll m)
    {
    	ll a=1,b=1;
    	if (m>n) return 0;
        while (m)
        {
        	a=(a*n)%p;
        	b=(b*m)%p;
        	m--;
        	n--;
        	
    	}
    	return ((ll)a*(ll)multi(b,p-2))%p;
    }
    
    ll lucas(ll n,ll m,ll p)
    {
    	if ( !m ) return 1;
    	else return ( (ll)lucas(n/p,m/p,p)*(ll)c(n%p,m%p)&p);
    }
    
    int main()
    {
    	cin>>t;
    	for (ll i=1;i<=t;i++)
    	{
    		cin>>n>>m>>p;
    		cout<<lucas(n+m,m,p)<<endl;
    	}
    	return 0;
    }

由于各种时间紧迫，悲剧的用了自带代码粘贴 各种悲剧 下次再改改吧

下一站就要转战DP海洋了···挣扎的小鱼啊···

但无论如何古诗词是不能少的

——凄凉别后两应同，最是不胜清怨月明中。

[Link 1]: http://blog.csdn.net/little_flower_0/article/details/46549557