SoundHound Programming Contest 2018 Masters Tournament,C: Not Too Close

https://soundhound2018-summer-final-open.contest.atcoder.jp/tasks/soundhound2018_summer_final_c

わりとすっきり解けた気がする。思考プロセス書きます。

N,D<=30
->分割統治?
->直線にしてみる?
->とりあえず緩和して最短距離がD以上のグラフの個数を数えてみる?
-->1から2への全ての経路がD以上になって見やすくなった。
-->bellman-ford的にdp?bfsっぽく距離1,2,3...の点と順番に見ていく?
--->後者っぽい。
--->dp[i][v][w]:=距離iの点まで見て、v個点が使われている。距離i-1で使われた点はw個。この時の場合の数　でできた。
--->緩和いらなくて草。
->こっからバグらせるんだよね。
-->dpにかかる係数をA,Bみたいに文字おいてごまかしたらわかりやすくなった。
-->困難は分割せよってそれ一番言われてる。

int N, D;

ll dp[41][41][41];

void solve() {
	cin >> N >> D;
	C_init(N);
	dp[0][1][1] = 1;
	rep(i, 0, D) {
		rep(v, 1, N) {
			rep(u, 1, N) {
				if(!dp[i][v][u]) continue;
				rep(w, 1, N) {
					ll A = mod_pow((mod_pow(2, u) - 1 + mod) % mod, w);
					ll B = mod_pow(2, w * (w - 1) / 2);
					ll E;
					if(i < D - 1) {
						if(N - v - 1 - w >= 0) E = C(N - (v + 1), w);
						else continue;
					}
					else if(i == D - 1) {
						if(N - v - w >= 0) E = C(N - (v + 1), w - 1);
						else continue;
					}
					else {
						if(N - v - w >= 0) E = C(N - v, w);
						else continue;
					}
					ADD(dp[i + 1][v + w][w], dp[i][v][u] * A % mod * B % mod * E % mod);
				}
			}
		}
	}
	ll res = 0;
	rep(i, 1, N + 1) {
		rep(j, 1, N) {
			ADD(res, dp[D][i][j] * mod_pow(2, j * (N - i) + (N - i) * (N - i - 1) / 2) % mod);
		}
	}
	cout << res << "\n";
}