TopCoder SRM 569 Div2 Hard MegaFactorialDiv2

続いてDiv2 Hard。
Div2 Hardは自分も何とか解き切れる位の問題が多くて、好みなんだよね。
http://community.topcoder.com/stat?c=problem_statement&pm=12400

問題

演算子!は以下の性質を持つ。

1. n>0, k>0ならn!k = (n-1)!k * n!(k-1)
2. n=0 なら n!k = 1
3. k=0 なら n!k = n

NとKが与えられたとき、N!Kの約数の数を答える問題。

解法

N!Kの素因数の数を数え上げて最後に１を足して全部掛け合わせればよい。
N<=1000, K<=100なので、A<=N, B<=KなA!BをDPで計算していけばよい。
ただ、1000以下の素数は150個程度あるため、A!Bのそれぞれについて150個分の素数の数を処理するとメモリが不足するようだ。

よって、以下の回答では、A!Bについてvectorを使い、小さなAについては150個分も素数の数を処理しないようにすることでメモリ量を削減した。

int np;
ll prime[200];
const int prime_max = 1001;
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;
	}
}

vector<int> dp[1001][101];
ll MO=1000000009;

class MegaFactorialDiv2 {
	public:
	int countDivisors(int N, int K) {
		int i,j,n,k;
		cprime();
		
		FOR(i,1001) {
			n=0;
			FOR(j,np) if(i%prime[j]==0) n=j;
			dp[i][0].resize(n+1);
			k=i;
			FOR(j,n+1) {
				dp[i][0][j]=0;
				if(k<prime[j]) break;
				while((k%prime[j])==0) {
					k /= prime[j];
					dp[i][0][j]++;
				}
			}
		}
		
		for(n=1;n<=1000;n++) for(k=1;k<=100;k++) {
			dp[n][k].resize(max(dp[n-1][k].size(),dp[n][k-1].size()));
			FOR(i,dp[n][k].size()) dp[n][k][i] = (
			((dp[n-1][k].size()>i)?dp[n-1][k][i]:0) + ((dp[n][k-1].size()>i)?dp[n][k-1][i]:0)) % MO;
		}
		
		ll res=1;
		FOR(i,dp[N][K].size()) {
			res = (res * (1LL+dp[N][K][i])) % MO;
		}
		return (int)res;
		
	}

};

まとめ

TopCoderでメモリ量の心配したの初めてな気がする…。