首页 > 代码库 > Number Sequence(hdu4390)
Number Sequence(hdu4390)
Number Sequence
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 895 Accepted Submission(s): 374
Please count how many number sequences a1,a2,...,an satisfy the condition that a1*a2*...*an=b1*b2*…*bn (ai>1).
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b1, b2,...,bn(1<bi<=1000000, b1*b2*…*bn<=1025).
题意:
给定b1---bn n个数,让你求出满足a1*a2*....*an-1*an(ai>1)=b1*b2*...*bn的种数。
思路:
先对每一个b分解质因数,统计每个质因子的个数,每个质因数不相互影响,可以单独考虑。首先考虑一种质因数放的总数,应明白 m个相同的数放进n个不同的盒子中(盒子可以为空)的总的种数为C(n-1,n+m-1).运用隔板法:实际上就是把m个数分成n组,每组可以为空,我们加上n-1个隔板,选出隔板所在的位置,相邻隔板之间的位置都放数,就有C(n-1,n+m-1)种了。
对每一质因数,运用上面的公式分别放进n个不同的盒子中,然后根据乘法原理,就能计算出答案了。
但是此时计算的答案并不是我们想要的,因为ai不能为1,故盒子不能为空,所以要用到容斥原理了。
运用容斥原理加上0盒子个为空的情况,减去k1*1个盒子为空的情况加上k2*2个盒子为空的情况...
k1、k2、ki怎样得到呢?
设 f[i]-放入i个数能够为空的种数,g[i]-放入i个数不能为空的种数,求g[n]。
考虑n=3时,
f[3]=g[3]+C(3,1)*g[2]+C(3,2)*g[1],
f[2]=g[2]+C(2,1)*g[1],
f[1]=g[1].
化简能得到g[3]=f[3]-C(3,1)*f[2]+C(3,2)*f[1].
根据数学归纳法能得到g[n]=f[n]-C(n,1)*f[n-1]+C(n,2)*f[n-2]-...
ps:http://acm.hdu.edu.cn/showproblem.php?pid=4390
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>using namespace std;#define FOR(i,a) for((i)=0;i<(a);(i)++)#define MEM(a) (memset((a),0,sizeof(a)))#define LL __int64const int N=1010;const int M=1000010;const LL MOD=1000000007;const int INF=0x7fffffff;const double eps=1e-7;const double PI=acos(-1.0);LL n,k,f[N],p[N],c[505][505];//c记录组合数,f记录因子,p记录对应因子数void init()//组合数[下a C b上] C(a,b)=C(a-1,b)+C(a-1,b-1);公式递归;{ for(LL i=0;i<=500;i++) { c[i][0]=c[i][i]=1; for(LL j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; }}LL work(){//容斥原理 LL temp,ans; ans=0; for(LL i=0;i<n;i++) { temp=c[n][i]; for(LL j=0;j<k;j++) temp=(temp*c[n-i+p[j]-1][n-i-1])%MOD;//c(n+m-1,n-1) if(i%2 == 0) ans=(ans+temp)%MOD; else ans=((ans-temp)%MOD+MOD)%MOD;; } return ans;}void Join(LL i,LL t){ LL j; for(j=0;j<k;j++) if(f[j] == i) { p[j]+=t; break; } if(j == k) { f[k]=i; p[k++]=t; }}int main(){ init(); LL a,i,j,t; while(scanf("%I64d",&n)!=EOF) { k=0; for(i=0;i<n;i++) { scanf("%I64d",&a); //求质因数及个数 t=0; for(j=2;j*j<=a;j++) { while(a%j==0) { a/=j; t++; } if(t>0) Join(j,t); } if(a>1) Join(a,1); } printf("%I64d\n",work()); } return 0;}
思路篇,需要好好体会。。。