AGC009E: Eternal Average

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点まともに解けたのは初めてかな?