Codeforces #240 Div1 B. Mashmokh and ACM

なんか典型っぽい問題…。
http://codeforces.com/contest/414/problem/B

問題

正の整数N,Kが与えられる。
K要素の正整数配列A[i]のうち：

• 各要素は1～Nの間である。
• A[i+1]はA[i]の倍数である。

そのような配列Aの数を求めよ。

解法

A[i]を先頭から決めていってDPすればよい。
配列要素数Kで値の最大値がNなので、状態数はO(KN)。

i番目の値がA[i]ならi+1番目の値はA[i], 2*A[i], 3*A[i]…と処理するの各状態でN/A[i]回処理する。
これはO(N)よりはだいぶ小さい(Nが1000でも平均7.5回)ので全体ではO(KN^2)よりだいぶ小さい。

int N,K;
ll dpdp[2001][2001];
ll mo=1000000007;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	dpdp[0][1]=1;
	
	FOR(i,K) {
		for(j=1;j<=N;j++) {
			for(k=j;k<=N;k+=j) dpdp[i+1][k]=(dpdp[i+1][k]+dpdp[i][j])%mo;
		}
	}
	ll ret=0;
	FOR(i,N) ret+=dpdp[K][i+1];
	cout << ret % mo << endl;
}

まとめ

余りにもヒネリのないオーソドックスなDP問題だ。
B問題としては珍しいな…。