HDU Number Sequence (容斥原理)

Number Sequence

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 63 Accepted Submission(s): 28

Problem Description

Given a number sequence b₁,b₂…b_n.
Please count how many number sequences a₁,a₂,...,a_n satisfy the condition that a₁*a₂*...*a_n=b₁*b₂*…*b_n (a_i>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 b₁, b₂,...,b_n(1<b_i<=1000000, b₁*b₂*…*b_n<=10²⁵).

Output

For each test case, please print the answer module 1e9 + 7.

SampleInput

2
3 4

SampleOutput

Hint

For the sample input, P=3*4=12. Here are the number sequences that satisfy the condition: 2 6 3 4 4 3 6 2

题目：给出n个数，b1,b2,b3……bn，构造n个数，a1,a2,……an(ai>1)，使得a1*a2*a3……an=b1*b2……bn;

http://acm.hdu.edu.cn/showproblem.php?pid=4390

首先是将所有的b进行素因子分解，则a和b的因子是完全一致的。

剩下的便是将所有b的因子，分给a

我们考虑某个素因子pi,如果有ci个，便成了子问题将ci个相同的物品放入到n个不同的容器中，种数为多少

但是要求ai>1，也就是容器不能为空，这是个问题。

我们考虑的是什么的情况，然后减去假设有一个确定是空的情况，发现可以用容斥原理解决

我们假设f[i]表示有i个容器的结果，c(n,i)*f[i]

将m个物品放到到不同的n个容器中，结果为c(n+m-1,n-1)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 
 9 const int mod=1000000007;
10 
11 long long c[510][510];
12 int n;
13 vector<int> vt;
14 
15 void Divide(int num){
16     for(int i=2;i*i<=num;i++)
17         while(num%i==0){
18             num/=i;
19             vt.push_back(i);
20         }
21     if(num>1)
22         vt.push_back(num);
23 }
24 
25 void Init(){
26     for(int i=0;i<=500;i++){
27         c[i][0]=c[i][i]=1;
28         for(int j=1;j<i;j++)
29             c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
30     }
31 }
32 
33 long long get(int n,int m){
34     return c[n+m-1][n-1];
35 }
36 
37 long long Solve(){
38     int a[1010]={1},cnt=0;
39     sort(vt.begin(),vt.end());
40     for(int i=1;i<vt.size();i++){
41         if(vt[i]!=vt[i-1])
42             a[++cnt]=1;
43         else
44             a[cnt]++;
45     }
46     long long ans=1;
47     for(int i=0;i<=cnt;i++)
48         ans=(ans*get(n,a[i]))%mod;
49     for(int i=1;i<n;i++){
50         long long tmp=c[n][i];
51         for(int j=0;j<=cnt;j++)
52             tmp=(tmp*get(n-i,a[j]))%mod;
53         if(i&1)
54             ans=((ans-tmp)%mod+mod)%mod;
55         else
56             ans=(ans+tmp)%mod;
57     }
58     return ans;
59 }
60 
61 int main(){
62 
63     //freopen("input.txt","r",stdin);
64 
65     Init();
66     while(~scanf("%d",&n)){
67         vt.clear();
68         int num;
69         for(int i=0;i<n;i++){
70             scanf("%d",&num);
71             Divide(num);
72         }
73         printf("%I64d\n",Solve());
74     }
75     return 0;
76 }