怎样求大组合数（取模）（ACM算法）比如我要求c（m1+m2,n）,(0 < n

怎样求大组合数（取模）（ACM算法）比如我要求c（m1+m2,n）,(0 < n
怎样求大组合数（取模）（ACM算法）
比如我要求c（m1+m2,n）,(0 < n

怎样求大组合数（取模）（ACM算法）比如我要求c（m1+m2,n）,(0 < n
这种题目然做过的,
意思比较简单,就由 m 个共 0 和 n 个 1 组成一个串,但从左到右要1出现的次数不少于0出现的次数.
由大牛的算法：结果就是 C(m+n,n) - C(m+n,m-1) 再取模,我们可以对式子化简一下就是：
(n+m)!*
(n-m+1) / ((m)!* (n+1)!)
再取模,但由于组合数很大,直接用大数乘除就会超时了,看了别人的报告才知道原来可以用素数化简快速求模的,n!= 2^p[i] *
3^p[i] * 5^p[i]*.再求模就可以很快了~(^ = ^)~.
#include
#include
#include
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000],p[150000],len; // prime 记录素数,p 记录素数的幂 len 记录长度
void getprime() // 筛法找素数
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; in>>m;
len = 0;
memset(p,0,sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加进 P 中去才能使 (m+n)!/ ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n,1);
get(m,0);
get(n+1,0);
ans = cal();
printf("%I64d\n",ans);
}
return 0;
}
可以用素数分解法,
先求出上面和下面的素数表示,然后约分后,再用求幂公式

这种题目然做过的，
意思比较简单，就由 m 个共 0 和 n 个 1 组成一个串，但从左到右要1出现的次数不少于0出现的次数。
由大牛的算法： 结果就是 C(m+n, n) - C(m+n, m-1) 再取模，我们可以对式子化简一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由于组合数很大，直接用大数乘除就会超时...

全部展开

这种题目然做过的，
意思比较简单，就由 m 个共 0 和 n 个 1 组成一个串，但从左到右要1出现的次数不少于0出现的次数。
由大牛的算法： 结果就是 C(m+n, n) - C(m+n, m-1) 再取模，我们可以对式子化简一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由于组合数很大，直接用大数乘除就会超时了，看了别人的报告才知道原来可以用素数化简快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。

#include
#include
#include
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 记录素数， p 记录素数的幂 len 记录长度
void getprime() // 筛法找素数
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素数分解, S为指数的加减(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 计算结果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //计算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加进 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}
可以用素数分解法，
先求出上面和下面的素数表示，然后约分后，再用求幂公式

收起