TopCoder SRM 532 Div1 Medium: DengklekBuildingRoads
解法
bitDP
tanzaku先生のコードを参考にした.
コード
public class DengklekBuildingRoads { private long MOD = (int) 1e9 + 7; private int K; private boolean[][][][] done; private long[][][][] dp; // nowを見た時に,残りedgeの辺が残っていて,start個以上離れた頂点から辺をnowに引いてくる場合の組み合わせの数 // maskは直前k個と自分の次数の偶奇の状態 private int bitDP(int now, int edge, int start, int mask) { if (edge == 0) { return mask == 0 ? 1 : 0; } if (now < 0) { return 0; } if (done[now][edge][start][mask]) { return (int) dp[now][edge][start][mask]; } long ans = 0; if ((mask & 1) == 0) ans += bitDP(now - 1, edge, 1, mask >> 1); for (int k = start; k <= K; k++) { if (k > now) break;// nowがまだ小さい時 int nextbit = mask; nextbit ^= (1 << 0);// 自分の分 nextbit ^= (1 << k);// k個離れた頂点の分 ans += bitDP(now, edge - 1, k, nextbit); } done[now][edge][start][mask] = true; dp[now][edge][start][mask] = ans % MOD; return (int) dp[now][edge][start][mask]; } public int numWays(int N, int M, int K) { this.K = K; done = new boolean[N][M + 1][K + 1][1 << (K + 1)]; dp = new long[N][M + 1][K + 1][1 << (K + 1)]; return bitDP(N - 1, M, 1, 0); } }
理解するのにすごく時間がかかってしまった.