[SCOI 第二试 字符串]求组合数、n!质因数分解

【题目】

Description

lxhgww最近接到了一个生成字符串的任务,任务需要他把n个1和m个0组成字符串,但是任务还要求在组成的字符串中,在任意的前k个字符中,1的个数 不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个,聪明的程序员们,你们能帮助他吗?

Input

输入数据是一行,包括2个数字n和m

Output

输出数据是一行,包括1个数字,表示满足要求的字符串数目,这个数可能会很大,只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

Hint

对于30%的数据,保证1<=m<=n<=1000
对于100%的数据,保证1<=m<=n<=1000000 【算法分析】
容易推得公式是C(n,n+m)-C(m-1,n+m)
然后就是求组合数问题。
然后n!有一个快速质因数分解的方法,按照那个分解,然后将除法变为幂减,最终再将个因子乘起来(要用快速幂)。就可以得解。
【CODE】
#include #include #include #include using namespace std;
const int N=2000000;
const int mod=20100403;
typedef long long lld;
bool ss[N+5];
int n1[N/10],n2[N/10],n3[N/10],pl[N/10];
int n,m,tot;
lld s1,s2;

void init(){
int i,j;
memset(ss,true,sizeof(ss));
for (i=2;i*i<=N;i++)
if (ss[i])
for (j=2;i*j<=N;j++)
ss[i*j]=false;
tot=0;
for (i=2;i<=N;i++)
if (ss[i]) pl[tot++]=i;
}

void Div(int *list,int n){
int i,j,tmp;
for (i=0;i for (i=0;i tmp=n;
while (tmp/pl[i]){
list[i]+=tmp/pl[i];
tmp/=pl[i];
}
}
}

lld pow(lld x,lld cf){
if (cf==0) return 1;
lld res=pow(x,cf/2);
res=(res*res)%mod;
if (cf%2) res*=x;
res%=mod;
return res;
}

int main(){
init();
scanf("%d%d",&n,&m);
Div(n1,m+n);
Div(n2,n);
Div(n3,m);
for (int i=0;i n1[i]-=n2[i];
n1[i]-=n3[i];
}
s1=1;
for (int i=0;i s1*=pow(pl[i],n1[i]);
s1%=mod;
}
Div(n1,m+n);
Div(n2,n+1);
Div(n3,m-1);
for (int i=0;i n1[i]-=n2[i];
n1[i]-=n3[i];
}
s2=1;
for (int i=0;i s2*=pow(pl[i],n1[i]);
s2%=mod;
}
lld ans=s1-s2;
ans=((ans%mod)+mod)%mod;
cout << ans << endl;
}

加入对话

6条评论

  1. 回复RP小魚兒:是的,这题可以,但是后来hdu月赛那题就不行了。用逆元处理的前提是:mod的数与除数互质。本题由于太过巧合,mod的数是素数,根本不需要逆元,直接欧拉定理即可。即:(a/b) mod p= a* b^(p-2) mod p(前提是p是素数)。

  2. 回复Moun_ElemeNt:逆元没有欧拉定理快,而且要满足的前提几乎和欧拉定理一样的。你去做hdu3398就知道了。就是本题,但mod的数不是素数,无法逆元。

留下评论

您的电子邮箱地址不会被公开。