题目链接:http://acm.ocrosoft.com/problem.php?cid=2659&pid=3
题目描述
猩猩,骆驼,还有泡泡经常喜欢在饭后到操场上散步,由于猩猩的走路姿势最突出最显眼,理所应当的成为他们中的主角,所以我的题目就说猩猩散步了。(骆驼和泡泡别有意见哈,和猩猩争啥……) 当然,话说回来,猩猩在OI上的能力也是不容低估的,你看,散步时还会想一道与此相关的问题,这是道经典的不能再经典的问题了。 在一个m×n的矩阵上,猩猩在左下角的顶点出现了,他只能沿着路径向上或者向右走,他的目标是“蠕动”到右上角的顶点,问他有多少路径可以选择。嗯,这个、这个、这个似乎地球人都知道怎么做,但是请注意,我有个条件没给呢!m和n现在的最大范围是50000,这可怎么办?仔细想想吧。
输入
只有一行,包含两个整数m和n,其上限均为50000
输出
由于最后的答案数目过大,所以只检查后100位,输出时每行十个数字,没空格间隔,共十行,如果答案位数没超过100位,则需要在空位上补0。
样例输入
7 4
样例输出
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000330
分析
题意就是求 C(n, m) ,需要用到高精度,可以先将组合数的元素进行素数分解,然后就能方便的用高精度算出答案了。
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define N 100005
typedef long long ll;
int cnt,prime[N],vis[N];
int n,m;
int a[N],p[N],len;
void Prime(int nn)
{
for(int i=2;i<=nn;i++)
{
if(!vis[i]) prime[++cnt] = i;
for(int j=1;j<=cnt&&i*prime[j]<=nn;j++)
{
vis[i*prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
void mul(int x)
{
for(int i=1;1ll*prime[i]*prime[i]<=1ll*x&&i<=cnt;i++)
{
while(x % prime[i] == 0)
{
x /= prime[i];
a[prime[i]]++;
}
}
if(x != 1) a[x]++;
}
void div(int x)
{
for(int i=1;1ll*prime[i]*prime[i]<=1ll*x&&i<=cnt;i++)
{
while(x % prime[i] == 0)
{
x /= prime[i];
a[prime[i]]--;
}
}
if(x != 1) a[x]--;
}
void cal(int x)
{
int i;
for(i=1;i<=len;i++) p[i] *= x;
i = 1;
while(i <= len || p[i] >= 10)
{
p[i + 1] += p[i] / 10;
p[i] %= 10;
i++;
}
len = i;
while(!p[len]) len--;
}
int main()
{
int T = 1;
//scanf("%d",&T);
while(T--)
{
len = 1;
p[1] = 1;
Prime(N);
scanf("%d%d",&n,&m);
for(int i=1;i<=min(n, m);i++) mul(n + m - i + 1);
for(int i=1;i<=min(n, m);i++) div(i);
for(int i=1;i<=n+m;i++)
{
if(a[i] == 0) continue;
for(int j=1;j<=a[i];j++)
{
cal(i);
}
}
for(int i=100;i>=1;i--)
{
printf("%d",p[i]);
if(i % 10 == 1) printf("\n");
}
}
return 0;
}
/*
50000 5000
*/