大师作文网怎样求大组合数（取模）（ACM算法）
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/12 23:52:45
怎样求大组合数（取模）（ACM算法）
比如我要求c（m1+m2,n）,(0 < n
比如我要求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;
}
可以用素数分解法,
先求出上面和下面的素数表示,然后约分后,再用求幂公式
再问： 嗯嗯，没错，素数分解是个好方法，我自己写的是450ms左右，题目限时是10s，说明真的挺高效的。ps.你给的程序不是求c(n,m)的吧，好像运行起来不是
再答： 思路是差不多的
意思比较简单,就由 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;
}
可以用素数分解法,
先求出上面和下面的素数表示,然后约分后,再用求幂公式
再问： 嗯嗯，没错，素数分解是个好方法，我自己写的是450ms左右，题目限时是10s，说明真的挺高效的。ps.你给的程序不是求c(n,m)的吧，好像运行起来不是
再答： 思路是差不多的