yukicoder : No.1532 Different Products

これはすんなり思い浮かぶかな。
https://yukicoder.me/problems/no/1532

問題

正整数N,Kが与えられる。
1～Nの部分集合のうち、積がK以下となるのは何通りか。

解法

Kが10^10と多いので、半分ずつ考えよう。
まず以下を考える。これらはO(Nk)で埋められるので、k≦√Kまで埋めよう。
L(n,k) := n以下の正整数のうち、積がkとなる要素の組み合わせの数。
R(n,k) := n以上の正整数のうち、積がkとなる要素の組み合わせの数。
RS(n,k) := n以上の正整数のうち、積がk以下となる要素の組み合わせの数。

まず、この時点でRS(1,√K)を求めれば√K以下のケースは列挙できる。
あとは、n未満の数字の部分集合にnを加えると初めて√Kを超えるケースを考えよう。

これはk*n≧√Kとなるkに対し、L(n-1,k)*RS(n+1,K/(k*n))を数えればよい。

int N;
ll K;

ll L[202][101010];
ll R[202][101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	L[0][1]=1;
	R[N+1][1]=1;
	for(i=N;i>=1;i--) {
		for(j=1;j<=100000;j++) {
			R[i][j]+=R[i+1][j];
			if(j*i<=100000) R[i][j*i]+=R[i+1][j];
			R[i+1][j]+=R[i+1][j-1];
		}
	}
	
	ll ret=0;
	for(i=1;i<=min(100000LL,K);i++) ret+=R[1][i];
	
	for(i=1;i<=N;i++) {
		for(j=1;j<=100000;j++) {
			L[i][j]+=L[i-1][j];
			ll a=1LL*i*j;
			if(a<=100000) {
				L[i][a]+=L[i-1][j];
			}
			else if(a<=K) ret+=L[i-1][j]*R[i+1][K/a];
		}
	}
	ret--;
	cout<<ret<<endl;
	
}

まとめ

そういえば何がDifferenceなんだろう。