SRM 532 div1 med: DengklekBuildingRoads

問題

TopCoder Statistics - Problem Statement

解法

直前 K 個 の頂点の次数の偶奇がわかっていれば, dp に持っていけそうです。

dp[now][restEdge][atLeast][flag] というように状態を与えます。
now 番目の頂点を見ていて, 残り貼る辺の数は restEdge で, now より前の頂点として, now-K+atLeast から先の頂点のみに辺を貼ることを考えます。また, 直前 K 個および自分の頂点までの次数の偶奇が flag で表される時の, valid なグラフの数, です。

atLeast はいらない子な気がするかもしれませんが, これがないと 「now-3 番目に辺を貼る -> now-1 番目に辺を貼る」 というのと, 「now-1 番目に辺を貼る -> now-3 番目に辺を貼る」というのが区別できないので, これも必要です。

dp の遷移にも注目です。僕は最初「1 つの頂点から 8 本に辺をはる方法なんてたくさんあって難しそう(小並感)」とか思ってましたが, それぞれの dp の遷移は, 「now から辺を貼るのはもう終わりにして次の頂点に行くか」というのと, 「now からどこかの頂点に辺を貼ってもう一回 now から辺を貼ることを考えるか」というのの 2 通りしかないです。

こんな感じの問題, 別の SRM の med で見た気がすると思ったらありました。
mayokoex.hatenablog.com

const ll MOD = 1e9+7;
// now, restEdge, atLeast, flag
ll dp[30][31][9][1<<9];
int N, M, K;

ll dfs(int now, int restEdge, int atLeast, int flag) {
    ll& ret = dp[now][restEdge][atLeast][flag];
    if (ret >= 0) return ret;
    if (restEdge == 0) {
        if (flag == 0) return 1;
        else return 0;
    }
    ret = 0;
    if (now < N-1) {
        if (now >= K) {
            if ((flag&1) == 0) ret += dfs(now+1, restEdge, 0, flag>>1);
        } else {
            ret += dfs(now+1, restEdge, 0, flag);
        }
    }
    int mini = max(0, now-K);
    for (int i = mini+atLeast; i < now; i++) {
        int nf = flag;
        nf ^= 1<<(now-mini);
        nf ^= 1<<(i-mini);
        ret += dfs(now, restEdge-1, i-mini, nf);
    }
    ret %= MOD;
    return ret;
}

class DengklekBuildingRoads {
public:
    int numWays(int N, int M, int K) {
        ::N = N, ::M = M, ::K = K;
        memset(dp, -1, sizeof(dp));
        return (int)(dfs(0, M, 0, 0));
    }
};