[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;
}