题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4390
题意:
有一个长度为n的序列,b1,b2,b3,,,,,bn;
寻找一个长度也为n的序列 使得满足以下条件
1) a1*a2*...*an=b1*b2*...*bn;
2)ai>1;
分析:
很明显就是把bi的所有素因子统计以下,然后重新组合分成n份。
我们先回顾以下一个子问题。
把m个相同的球分到n个不相同的容器里,每个容器能为空。
挡板法:
ans = C(n+m-1,n-1);
然后我们就来了思路了 因为ai大于1,说明不能为空。我们可以从反面
来考虑,先求出一共所有的方案数num1,然后再通过容斥原理来求出,至少
存在一个为空的方案数num2。
ans = num1 - num2.
代码如下:
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1005; const int MOD=1000000007; int p[maxn]; int a[maxn]; LL c[maxn][maxn]; void init(){ int i,j; for(i=0;i<maxn;i++){ c[i][i]=c[i][0]=1; for(j=1;j<i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; } } int getnum(int m,int n){ return c[m+n-1][n-1]; } LL solve(int cnt,int n){ int i,j; LL ans=1; for(i=0;i<=cnt;i++) ans=(ans*getnum(a[i],n))%MOD; for(i=1;i<n;i++) { LL tmp=c[n][i]; for(j=0;j<=cnt;j++) tmp=(tmp*getnum(a[j],n-i))%MOD; if(i&1) ans=((ans-tmp)%MOD+MOD)%MOD; else ans=(ans+tmp)%MOD; } return ans; } int main() { init(); int n; while(~scanf("%d",&n)) { int t,i,j; int cnt=0; for(i=0;i<n;i++){ scanf("%d",&t); for(j=2;j*j<=t;j++){ while(t%j==0){ p[cnt++]=j; t/=j; } } if(t>1) p[cnt++]=t; } sort(p,p+cnt); a[0]=1; i=0; for(j=1;j<cnt;j++){ if(p[j]==p[j-1]) a[i]++; else a[++i]=1; } cnt=i; printf("%I64d\n",solve(cnt,n)); } return 0; }
原文:http://blog.csdn.net/bigbigship/article/details/44567445