【今日の精進】CF16-FINALF - Road of the King

毎日格上の問題を倒すやつの37日目です。

問題リンク

atcoder.jp

問題概要

頂点 辺のグラフがあるよ。

はじめ、王様が頂点 にいるよ。長さ の数列 を決めて、 回以下の行動を繰り返すよ。

• 今いる頂点から頂点 の向きに辺を張り、 に移動する

このとき、どの頂点間にも経路が存在するような の数を で割った余りを求めてね。

解法

全ての頂点が強連結であることが明らかに必要十分条件です。

また、辺を張っていく最中、「頂点1と強連結な頂点」「強連結ではないが通った頂点」「通ってない頂点」のように分けれることが示せます。

そのため、これらを情報にもってDPしましょう。

具体的には、以下のようにすれば良いです。

• 「頂点1と強連結な頂点」に行く場合…「強連結ではないが通った頂点」がすべて「頂点1と強連結な頂点」になる
• 「通ってない頂点」に行く場合…「強連結ではないが通った頂点」が一つ増える
• 「強連結ではないが通った頂点」に行く場合…何も起きない

提出コード

MOD=10**9+7
N,M=map(int,input().split())
dp=[[[0]*(N-i+2) for i in range(N+1)] for j in range(M+1)]
dp[0][1][0]+=1
for i in range(M):
    for j in range(N+1):
        for k in range(N-j+1):
            if dp[i][j][k]==0:
                continue
            dp[i][j][k]%=MOD
            dp[i+1][j][k]+=dp[i][j][k]*k
            dp[i+1][j+k][0]+=dp[i][j][k]*j
            dp[i+1][j][k+1]+=dp[i][j][k]*(N-j-k)
print(dp[-1][N][0]%MOD)

Submission #46955691 - CODE FESTIVAL 2016 Final

感想

DPとわかるまでが難しい定期