kmjp's blog

競技プログラミング参加記です

AtCoder ARC #107 : D - Number of Multisets

想定解賢いなぁ。
https://atcoder.jp/contests/arc107/tasks/arc107_d

問題

正整数N,Kが与えられる。
N個の(1/2)^i (iは0以上の整数)の多重集合のうち、総和がKとなるのは何通りか。

解法

O(N^3)でもどうにか通る。
最初、1がK個あるとし、これらのうち最小値を2分割することを繰り返し、計N個となることを考えよう。
f(a,b) := 現在要素がa個あり、最小値が(値は問わず)b個ある
とする。f(K,K)=1から初めて、f(N,*)の総和を求めよう。
bのうちx個を分割するとして、f(a,b)をf(a+x, 2x)に加算する、ということを各a,b,xにおいて繰り返していくとよい。

EditorialはO(N^2)解法。
f(a,b) := a個の要素の総和でbを作る作り方
とする。f(a,a)=1から初めて、f(N,K)を求めよう。
最大要素として1を用いる場合と、1を用いない場合を考える。1を用いないときの構成法はf(a,2b)なので、
f(a,b) = f(a-1,b-1) + f(a,2b)
でf(a,b)を求めて行けばよい。

以下のコードは両方記載している。前者はコメントアウト内。

int N,K;
const ll mo=998244353;

int dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	dp[1][1]=1;
	for(i=2;i<=N;i++) {
		for(j=N;j>=1;j--) {
			dp[i][j]=dp[i-1][j-1];
			if(j*2<=i) (dp[i][j]+=dp[i][2*j])%=mo;
		}
	}
	cout<<dp[N][K]<<endl;
	
	/*
	dp[K][K]=1;
	
	for(i=K;i<N;i++) {
		for(y=1;y<=N;y++) if(dp[i][y]) {
			for(x=1;x<=y&&i+x<=N;x++) {
				dp[i+x][2*x]+=dp[i][y];
				if(dp[i+x][2*x]>=mo) dp[i+x][2*x]-=mo;
			}
		}
	}
	ll ret=0;
	FOR(i,N+1) ret+=dp[N][i];
	cout<<ret%mo<<endl;
	*/
	
}

まとめ

O(N^3)は想定内なのかな。