A. On Number of Decompositions into Multipliers
题目连接：http://codeforces.com/contest/396/problem/A
大意：给定n(n<=500)个数ai(1<=ai<=10^9)，得到他们的乘积m，问将m分解成n个数相乘，有多少种方法.
思路：显然每个质因数都是独立的，如果质因数pi出现了ci次，那么把它分到n个数中，就有C(ci+n-1,n-1)种方法，然后把所有因数的答案相乘就是结果。于是我们可以先预处理出来组合数。然后对每个ai进行分解因式，最后的复杂度O(n*sqrt(max(ai))).
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <functional>
#include <cmath>
typedef long long ll;
using namespace std;
const ll mod = ;
map<ll,ll> cnt; int n;
ll a[];
ll c[][];
int main(){
freopen("in.txt","r",stdin);
ios::sync_with_stdio();
c[][] = ;
for(int i=;i<;i++){
for(int j=;j<=min(i,);j++){
if(j== || j==i)
c[i][j] = ;
else
c[i][j] = ( c[i-][j-] +c[i-][j] )%mod;
}
}
cin>>n;
for(int i=;i<n;i++){
cin>>a[i];
} for(int i=;i<n;i++){ for(ll j=;j*j<=a[i];j++){ if(a[i]%j==){
ll tmp = ;
while(a[i]%j==){
a[i]/=j;
tmp++; }
cnt[j]+=tmp; } }
if(a[i]!=)
cnt[a[i]]++; } ll ans = ; for(map<ll,ll>::iterator i = cnt.begin();i!=cnt.end();i++){
ll cc =(*i).second; ans = (ans*c[cc+n-][n-])%mod;
} cout<<ans%mod<<endl;
return ;
}