Codeforces Round #232 (Div. 1) 解题报告

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-02-26 23:26
 5  * Filename     :
 6  * Description     :
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int MOD = 1000000007;
34 ll C[20010][510];
35 map<ll, ll> mp;
36 
37 const int MAXN=1000000;
38 int prime[MAXN+1];
39 void getPrime()
40 {
41     memset(prime,0,sizeof(prime));
42     for(int i=2; i<=MAXN; i++)
43     {
44         if(!prime[i])prime[++prime[0]]=i;
45         for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++)
46         {
47             prime[prime[j]*i]=1;
48             if(i%prime[j]==0) break;
49         }
50     }
51 }
52 
53 void make(int n){
54     int temp = sqrt(n);
55     for(int i=1; prime[i] <= temp; i++){
56         while(n%prime[i]==0){
57             mp[prime[i]]++;
58             n/=prime[i];
59         }
60     }
61     if(n>1) mp[n] ++;
62 }
63 
64 void init(){
65     memset(C, 0, sizeof C);
66     C[0][0] = 1;
67     for(int i=0; i<20010; i++){
68         C[i][0] = 1;
69         if(i < 510)C[i][i] = 1;
70         for(int j=1; j<min(510, i); j++){
71             C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
72         }
73     }
74 }
75 
76 int main()
77 {
78 //    freopen("in.txt", "r", stdin);
79 
80     int n, tnum;
81     while(scanf("%d", &n)!=EOF){
82         init();getPrime();mp.clear();
83         for(int i=0; i<n; i++){
84             scanf("%d", &tnum);
85             make(tnum);
86         }
87         ll ans = 1, tans;
88         for(map<ll, ll>::iterator it=mp.begin(); it!=mp.end();++it){
89             tans = 0;
90             for(int j=0; j<n; j++) {
91                 tans = (tans+(C[n][j+1]*C[it->second-1][j])%MOD)%MOD;
92             }
93             ans = ans * tans;
94             ans%=MOD;
95         }
96         printf("%I64d\n", ans);
97     }
98     return 0;
99 }