求组合数
因为数据范围较大且要乘除所以想当然的使用高精了,无脑使用高精的话复杂度又会非常高。
所以当这种数学题目写不出来时则想着能不能改变式子。
而这个式子最花时间的是什么?
当然是阶乘。
分解质因数
为什么分解质因数?这个问题真的是难到我自己了。
因为当时看录像没有听太明白所以一下子真想不到,看所有题解也并不是很懂。
你既然能分解N!的质因子那理所当然M!的质因子也能分解,那这么说的话(N-M)!的质因子也一定能分解。
看到这应该也看明白了,C(N,M)=N!/M!/(N-M)!
求出质因子的用途就很想当然了我们可以把它的所有质因子乘起来这样既可得到最终答案。
而直接求出上面式子有些许困难我们不如直接求出N!的质因子接着减去这些除数的质因子。
这样就得出了答案所有的质因子。
得出质因子的数量
关于这个没什么好说的,因为在纸上写些例子就会明白。
int fj(int x,int y)
{
int s=0;
while(x)s+=x/y,x/=y;
return s;
}
代码
#include<vector>
#include<cstdio>
#define vtt vector<int>
using namespace std;
const int sz=5001;
int n,m,f[sz],zs[sz],sm[sz],pm;
vtt s;
void ycl(int x)
{
int i,j;
for(i=2;i<=x;++i)
{
if(!f[i])zs[++pm]=i;
for(j=1;zs[j]<=x/i;++j)
{
f[i*zs[j]]=1;
if(i%zs[j]==0)break;
}
}
}
int fj(int x,int y)
{
int s=0;
while(x)s+=x/y,x/=y;
return s;
}
vtt cf(vtt a,int b)
{
int i,x=0;vtt c;
for(i=0;i<a.size();++i)
{
x+=a[i]*b;
c.push_back(x%10);
x/=10;
}
while(x)c.push_back(x%10),x/=10;
return c;
}
int main()
{
int i,j;s.push_back(1);
scanf("%d%d",&n,&m);
ycl(n);
for(i=1;i<=pm;++i)sm[i]=fj(n,zs[i])-fj(m,zs[i])-fj(n-m,zs[i]);
for(i=1;i<=pm;++i)
for(j=1;j<=sm[i];++j)s=cf(s,zs[i]);
for(i=s.size()-1;i>=0;--i)printf("%d",s[i]);
return 0;
}
废话
兴许以后复习时看到这里的我应该会觉得很啰嗦但你别忘记当初你可是花了一个小时多才写出来的啊!!!
能不能注释一下,
tql大佬 代码解释的很清晰 orzorz
爱你哟tql
爱你,佬
lp