周赛 1007 例题 hdu 4390 Number Sequence （质因数分解+组合数学+容斥原理）
周赛 1007 题解 hdu 4390 Number Sequence （质因数分解+组合数学+容斥原理）
Number Sequence
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 790 Accepted Submission(s): 331
Problem Description
Given a number sequence b1,b2…bn.
Please count how many number sequences a1,a2,...,an satisfy the condition that a1*a2*...*an=b1*b2*…*bn (ai>1).
Please count how many number sequences a1,a2,...,an satisfy the condition that a1*a2*...*an=b1*b2*…*bn (ai>1).
Input
The input consists of multiple test cases.
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).
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).
Output
For each test case, please print the answer module 1e9 + 7.
Sample Input
2 3 4
Sample Output
4HintFor the sample input, P=3*4=12. Here are the number sequences that satisfy the condition: 2 6 3 4 4 3 6 2
Source
2012 Multi-University Training Contest 10
题意：
给定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)种了。
给定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]-...
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 20005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
ll n,m,ans,cnt,tot,flag;
ll C[1005][25];
map<ll,ll>mp;
map<ll,ll>::iterator it;
int main()
{
ll i,j,t,p;
for(i=0;i<=1000;i++) // 预处理组合数
{
C[i][0]=1;
}
for(i=1;i<=1000;i++)
{
for(j=1;j<=20;j++)
{
C[i][j]=C[i-1][j]+C[i-1][j-1];
C[i][j]%=mod;
}
}
while(cin>>n)
{
mp.clear();
ll x,y;
for(i=1;i<=n;i++)
{
cin>>t;
y=sqrt(t+0.5);
for(j=2;j<=y&&t>1;j++) // 质因数分解
{
if(t%j==0)
{
while(t%j==0)
{
t/=j;
mp[j]++;
}
}
}
if(t>1) mp[t]++;
}
ans=0;p=1;
for(i=0;i<n;i++)
{
ll tmp=C[n][i];
for(it=mp.begin(); it!=mp.end(); it++)
{
t=it->second;
x=t+n-1-i;
tmp*=C[x][n-1-i];
tmp%=mod;
}
ans+=p*tmp+mod; // 中途可能出现为负数 需加上mod 或者在最后加上再模也可以
ans%=mod; p=-p;
}
cout<<ans<<endl;
}
return 0;
}