Codeforces 396(#232 Div1) A. On Number of Decompositions into Multipliers

問題

n個の数aiが与えられる。
m = a1 * a2 * ... * anとする。
mをn個の数の積b1 * b2 * ... * bnとしてあらわす方法は何通りあるかmod 10^9 + 7で答えよ。

制約条件

n≦500
ai≦10^9

方針

素因数ごとに独立して、n個に割り振る場合の数を求めて掛けるだけ。

なんでこんなのが解けなかったのかorz
ブランクで典型問が解けない病になっている。酷い。UTPCオンサイト大丈夫だろうか。

ソースコード

const int mod = (int)1e9 + 7;
int n, dp[501][20000];
map<int, int> e;

int main(){
	cin >> n;
	
	dp[0][0] = 1;
	rep(i, n) rep(j, 20000){
		dp[i + 1][j] = (j ? dp[i + 1][j - 1] : 0) + dp[i][j];
		dp[i + 1][j] %= mod;
	}
	
	rep(i, n){
		int a; cin >> a;
		for(int j = 2; (ll)j * j <= a; j++) if(a % j == 0){
			int c = 0;
			for(; a % j == 0; a /= j) c++;
			e[j] += c;
		}
		if(a > 1) e[a]++;
	}
	ll ans = 1;
	each(i, e) ans = ans * dp[n][i->second] % mod;
	cout << ans << endl;
	
	return 0;
}