題目描述:
給出n個數,b1,b2,b3……bn,構造n個數,a1,a2,……an(ai>1),使得a1*a2*a3……an=b1*b2……bn;
問一共有多少種數列a1,a2,……an滿足上述條件。
輸入:
包含多組輸入資料
每組資料第一行有1個整數n(1<=n<=20)
每組資料第 二行有n個整數第i個數表示bi.(1<bi<=1000000)且b1*b2*…*bn <10^25)。
輸出:
對于每組測試資料,輸出有多少種數列滿足情況,結果對1e9+7取餘
輸入樣例:
2
3 4
輸出樣例:
4
提示:
無
思路分析:
想一想,如果它們的積相等則它們的質數唯一分解就相等。
畢竟是方案數,那麼排列組合是一定的,那麼我們先遞推出組合數。
然後就是求解了。
我們可以這樣想,指數就是特産的個數,而不同的底數就是特産,而n就是人數。
先考慮一種特産的情況:
可以使用容斥原理。設S表示全集,Pi表示至少有i個人沒有分到特産的方案數。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL0gTOyMTNyMTM1IzMwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
設該特産的數量為m,人數為n,由于S全集含有沒分到的情況,可采用補人數個球的隔闆法求得S,Pi求法可以從n個人中選出i個人,強制他們為空,剩下的用隔闆法即可
然後考慮多種特産的情形,發現适用乘法原理:
其中Pij表示至少有j個人沒有分到第i種特産的方案數。
代碼實作:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll n,m,k,w[1005],p[1005],c[1005][1005],mod=1e9+7,tot;
void C()
{
for(int i=0;i<=1000;i++)
{
c[i][0]=1;
c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
ll deal()
{
ll ans=1;
for(int i=0;i<=tot;i++)
ans=(ans*c[w[i]+n-1][n-1])%mod;
for(int i=1;i<n;i++)
{
ll z=c[n][i];
for(int j=0;j<=tot;j++)
z=(z*c[w[j]+n-i-1][n-i-1])%mod;
if(i&1)
ans=((ans-z)+mod)%mod;
else
ans=(ans+z)%mod;
}
return ans;
}
int main()
{
C();
while(scanf("%lld",&n)!=-1)
{
ll x;
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
for(int j=2;j*j<=x;j++)
{
if(x%j==0)
{
while(x%j==0)
{
p[tot++]=j;
x/=j;
}
}
}
if(x>1)
p[tot++]=x;
}
sort(p,p+tot);
ll len=0;
w[0]=1;
for(int j=1;j<tot;j++)
{
if(p[j]==p[j-1])
w[len]++;
else
{
len++;
w[len]=1;
}
}
tot=len;
printf("%lld\n",deal());
}
}