kmjp's blog

競技プログラミング参加記です

TopCoder SRM 711 Div1 Medium OrderedProduct

今回時間だけ見ればみなEasyと大差ないし、これ450ptでもいい気がする。
https://community.topcoder.com/stat?c=problem_statement&pm=14550

問題

p[i]をi番目の素数、a[i]をその指数とし、それから生成される値Xを \displaystyle X=\prod_{i=0}^n p_i^{a_i}とおく。
以下の条件を満たす数列はいくつあるか求めよ。

  • 各要素は1より大きな整数である。
  • 全要素の積はXである。

解法

以下を考えると、sum(dp(L))が解となる。
dp(L) := 条件を満たす長さLの数列の数

ここで、要素数Lの数列がどうすれば条件を満たすかを考える。
今回の条件を満たすには、まず各要素1の数列を準備し、結局各素数p[i]を合計a[i]いずれかの要素に掛ける、ということを繰り返す。
ただし、1のままの要素が残っていてはならない。

前者については重複組み合わせで \displaystyle \prod_i {}_L H_{a_i}を求めればよい。
あとは包除原理の要領で1のままの要素が残っているケースを引こう。
L個中ちょうどK個しか1より大きな値が入っていないケースは、 \displaystyle \prod_i {}_L C_K \times dp(K)通りなので、K<Lの各Kに対し、左の値を引いていこう。

ll mo=1000000007;
ll dp[3000];

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}


class OrderedProduct {
	public:
	int count(vector <int> a) {
		
		int sum=0;
		FORR(r,a) sum+=r;
		int i,j;
		ll ret=0;
		for(i=1;i<=sum;i++) {
			dp[i]=1;
			FORR(r,a) {
				(dp[i] *= hcomb(i,r))%=mo;
			}
			for(j=1;j<i;j++) {
				(dp[i] += mo - dp[j]*combi(i,j)%mo)%=mo;
				
			}
			ret += dp[i];
		}
		return ret%mo;
		
	}
}

まとめ

どっかでこの問題出てそう。