想定解賢いなぁ。
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)は想定内なのかな。