首页 > 代码库 > POJ 2992

POJ 2992

2024-07-22 07:57:53   227人阅读

此题A得艰难，应该是有很多组数据吧，使得容易超时。

直接求出组合数是不可能的，因而，只能把各个数都计算其各素因子个数，再计算即可。

而直接计算，必定是要超时的，所以，只好先预处理所有结果，再输出了。

首先筛选素数，分解0~440的素因子。

然后，Cnk=(n*(n-1)*(n-2)*...(n-k+1))/k!，计算，按各数所拆解素因子计算出组合数的素因子及其个数，再求出即可。

而对于Cn(k+1)=(n*(n-1)*(n-2)*...(n-k+1)*(n-k))/(k+1)!只需在Cnk的基础上递推过来，亦即再加上n-k的素因子个数减去k+1素因子个，否则，TLE

#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;bool isprime[500];int prime[500],np;int cnum[500][500];__int64 Cnk[500][500];void prim(){	int Max=500;	memset(isprime,true,sizeof(isprime));	memset(cnum,0,sizeof(cnum));	np=0;	int i,j;	isprime[1]=false;	for(i=2;i<Max;i++){		if(isprime[i]){			prime[np++]=i;			for(j=i*i;j<Max;j+=i)			isprime[j]=false;		}	}		memset(cnum,0,sizeof(cnum));	for(int i=440;i>=0;i--){		int tmp=i;		for(int j=0;prime[j]<=tmp;j++){			if(tmp%prime[j]==0){				while(tmp%prime[j]==0){					cnum[i][j]++;					tmp/=prime[j];				}			}		}	}	}void divide(){	int ans[500];	for(int n=0;n<=440;n++){		for(int k=0;k<=n;k++){			Cnk[n][k]=1;			if(k==0){ continue; }			if(k==1){				for(int i=0;i<np;i++){					ans[i]=cnum[n][i];				}			}			else{				for(int i=0;i<np;i++){					ans[i]=ans[i]+cnum[n-k+1][i]-cnum[k][i];				}			}			for(int i=0;i<np;i++)			Cnk[n][k]*=(__int64)(ans[i]+1);		}	}}int main(){	int n,k,tmp;	prim();	divide();	while(scanf("%d%d",&n,&k)!=EOF){		printf("%I64d\n",Cnk[n][k]);	}	return 0;}

　　

POJ 2992


联系
我们