https://agc009.contest.atcoder.jp/tasks/agc009_e
まずK分木の葉に0や1を書き込んで、木の形状通りに平均を取っていく問題に言い換えます。
するとK分木は葉が全て0の部分を除けば、縦1直線に繋げばいいことがわかります。
証明のアイディアとしては、葉が全て1の木を一番深いところに生えている1が書き込まれた葉と入れ替える感じです。
こうすることで一番深いところに生えている葉はK枚、ほかの階層は(K-1)枚となりました。
あとはdp[i][j][k]:=(深さiまで見て、j個葉に1を書き込み、繰り上がりがk(0or1)の時の操作後の最終的な値としてあり得るものの場合の数)
の桁DPをしてO((N+M)^2)で解けます。
桁DPも多分するのは初めて?で結構戸惑いましたけど、背反であることを確認しながらやればそんな難しくはないですね。
ll dp[2][4010][2]; int N, M, K, T; void solve() { cin >> N >> M >> K; int T = (N + M - 1) / (K - 1); int now = 0, nex = 1; dp[now][0][0] = 1; rep(i, 0, T) { memset(dp[nex], 0, sizeof(dp[nex])); rep(j, 0, M + 1) { rep(k, 0, 2) { if(!dp[now][j][k]) continue; if(j == 0) { assert(k == 0); rep(cnt, 0, K) { ADD(dp[nex][j + cnt][0], dp[now][j][k]); } ADD(dp[nex][j + K][1], dp[now][j][k]); } else { if(k == 0) { rep(cnt, 0, K) { ADD(dp[nex][j + cnt][0], dp[now][j][k]); } } else { rep(cnt, 0, K - 1) { ADD(dp[nex][j + cnt][0], dp[now][j][k]); } ADD(dp[nex][j + K - 1][1], dp[now][j][k]); } } } } swap(now, nex); } cout << dp[now][M][0] << "\n"; }
1600点まともに解けたのは初めてかな?