kmjp's blog

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

TopCoder SRM 565 Div2 Hard DivisibleSequence

Div2 Hardも挑戦。
Div1 Mediumとは別だけど、これはこれで面白い問題。
今回はDiv1 Mediumの方が難しいかな。
http://community.topcoder.com/stat?c=problem_statement&pm=12274

数Nが与えられ、H個の数列を作る。数列の各要素は前の数の約数でなくてはいけない。
このような数列の取り方を列挙する。

まず、数Nを素因数分解して行く。
各素因数の次数がCの時、その素因数で割る位置の取り方は\sum_{i=0}^C {}_{H-1} H_i = \sum_{i=0}^C {}_{H-i-2} C_iなので、これを掛け合わせていく。

Hは10^9とかなり大きいが、Cはlog_2 10^9=30なので、1~30のmod 1000000009における逆元を取っておけばすんなり計算できる。

int np;
ll prime[100000];
const int prime_max = 1000001;
void cprime() {
	int i,j;
	char p[prime_max];
	
	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}

ll mod=1000000009;
ll rev(ll num) {
	ll pw = mod-2;
	ll ret = 1;
	for(ll i = 30; i >= 0; i--) {
		ret = (ret*ret)%mod;
		if((pw>>i)&1) ret = (ret*num)%mod;
	}
	return ret;
}

ll combi(ll N_, ll C_) {
	const int num=100;
	static ll rm[num+1];
	int i;
	ll res=1;
	if(rm[1]==0) for(i=1;i<=num;i++) rm[i]=rev(i);
	
	assert(C_<num);
	
	FOR(i,C_) {
		res = (res * rm[i+1])%mod;
		res = (res * (N_-i))%mod;
	}
	return res;
}


class DivisibleSequence {
	public:
	int count(int N, int H) {
		int i;
		cprime();
		ll res=1;
		
		if(H==1) return 1;
		FOR(i,np) {
			ll tres = 1;
			int nd=0;
			while(N%prime[i]==0){ N /= prime[i]; nd++; tres += combi(H+nd-2,nd);}
			res = (res*tres)%mod;
		}
		if(N>1) res = (res*H) % mod;

		return res;
	}
};

まとめ

{}_P C_QはPが大きくても、Qが小さかったりmodがついている場合は逆元を使ってうまく処理できる。
これは以前に練習したことだな。
重複組み合わせと合わせて、勉強の成果が出たね。