题目链接：
?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;elseans=(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]++;elsea[++i]=1;}cnt=i;printf("%I64d\n",solve(cnt,n));}return 0;}
没有伞的孩子必须努力奔跑！
