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

CF230に続いてなんとか２ケタ順位を取り、年末の好調レートまで戻せた。
http://codeforces.com/contest/396/problem/A

問題

N要素の自然数配列A[i]が与えられる。
N要素の自然数の配列B[i]のうち、全要素の積がA[i]の全要素の積と一致するものの組み合わせを答えよ。

解法

まず、B[i]の積がA[i]の積と一致するので、A[i]の各要素を素因数分解し、全部の積の素因数分解を行おう。
後は各素因数をN個のB[i]にそれぞれ分類すればよい。
ある素因数xの数がP(x)個あるなら、その素因数をN個に分ける方法は重複組み合わせでを掛け合わせるだけ。

int N;
ll A[1001],t;
ll mo=1000000007;
map<ll,int> M;

ll combi(ll N_, ll C_) {
	int i;
	const int num=20000;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[mo%i]*(mo-mo/i)%mo;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%mo;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * ((N_-i)%mo))%mo;
	return ret;
}
ll hcomb(int P_,int Q_) { return combi(P_+Q_-1,Q_);}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) {
		cin>>t;
		for(ll a=2;a*a<=t;a++) {
			while(t%a==0) t/=a,M[a]++;
		}
		if(t>1) M[t]++;
	}
	
	
	ll ret=1;
	ITR(it,M) {
		ret = (ret * hcomb(N,it->second)) % mo;
	}
	cout << ret << endl;
	
}

まとめ

Aの割に実装が面倒で、みんな出だしはゆっくり目だったね。
自分も9分とそこそこかかったけど、悪くない出だし。