AtCoder ABC #132 : F - Small Products

しょうもないミスを繰り返した。
https://atcoder.jp/contests/abc132/tasks/abc132_f

問題

整数N,Kが与えられる。
K要素の正整数列のうち、隣接要素の積がNを超えないものは何通りか。

解法

Nが小さければ自明である。
f(n,m) := n要素の条件を満たす数列のうち末尾の要素がmであるもの
とすると
f(n+1,k) = sum(f(n,m)) (m*k≦N)
を計算していけばよい。

さて、ここでkが大きい場合、mと取れる範囲はかなり小さくなることに気付く。
そこで、大きな値kはN/kが一致する範囲でまとめてしまおう。
具体的にはNを2√N通り程度に分類する。
前半√N個には1～√Nが1個ずつ入り、後半√N個は、N/kが1～√Nになる範囲を入れる。

あとは累積和を使いつつ上記式を数え上げていこう。

ll N,K;
ll mo=1000000007;

vector<pair<ll,ll>> V;
int tar[150505];

ll from[101010];
ll S[101010];
ll to[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	for(i=1;;i++) {
		V.push_back({i,i});
		if(i*i>N) break;
	}
	i++;
	V.push_back({i,i});
	while(i>=1) {
		ll L=N/(i+1)+1;
		ll R=N/i;
		//cout<<L<<" "<<R<<endl;
		L=max(L,V.back().second+1);
		if(L<=R) V.push_back({L,R});
		i--;
	}
	
	while(V.back().first>N) V.pop_back();
	V.back().second=min(V.back().second,N);
	
	FOR(i,V.size()) {
		x=0;
		for(j=20;j>=0;j--) if(x+(1<<j)<V.size() && 1LL*V[i].second*V[x+(1<<j)].second<=N) x+=1<<j;
		tar[i]=x;
		from[i]=V[i].second-V[i].first+1;
		//cout<<i<<" "<<V[i].first<<" "<<V[i].second<<" "<<tar[i]<<endl;
	}
	
	
	K--;
	while(K--) {
		FOR(i,V.size()) S[i+1]=(S[i]+from[i])%mo;
		FOR(i,V.size()) to[i]=S[tar[i]+1]*(V[i].second-V[i].first+1)%mo;
		swap(from,to);
	}
	
	ll ret=0;
	FOR(i,V.size()) ret+=from[i];
	cout<<ret%mo<<endl;
	
}

まとめ

ミスが多すぎるのいかんなぁ。