yukicoder : No.2846 Birthday Cake

これはすんなり思いつけた。
https://yukicoder.me/problems/no/2846

問題

正整数N,Kが与えられる。
1以上N以下の整数nに対する1/nの形の分数を、K個和を取って1となるようにしたい。
各分数の組み合わせは何通りか。

解法

Kの上限が24なので、K/2以上の素数、すなわちn=13,17,19,23となる分数を使おうとすると、1/nをn個集めて和を1にするの一択である。
これらの素数を除くと、1～24の最小公倍数は2^4*3^2*5*7*11である。
よって、各分母を(2^4*3^2*5*7*11)にそろえたうえで、和が2^4*3^2*5*7*11となるようにDPで組み合わせを数え上げて行けばよい。

int N,K;
const ll ma=2*2*2*2*3*3*5*7*11;
ll from[ma+1];
ll to[ma+1];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	from[0]=1;
	FOR(i,K) {
		ZERO(to);
		for(k=1;k<=N;k++) if(ma%k==0) {
			FOR(j,ma-(ma/k)+1) if(from[j]) {
				to[j+ma/k]+=from[j];
			}
		}
		swap(from,to);
	}
	
	ll ret=from[ma];
	if(K==13&&N>=13) ret++;
	if(K==17&&N>=17) ret++;
	if(K==19&&N>=19) ret++;
	if(K==23&&N>=23) ret++;
	cout<<ret<<endl;
	
}

まとめ

K,Nの上限が25だとちょっと厳しいかな。