mayoko’s diary

プロコンとかいろいろ。

SRM 669 div1 med:LineMST

本番いいところまでいったと思ってたけど全く的はずれだったらしい。

解法

MST かつ line であるようなものとして, 0-1-...-(n-1) というのだけ抑えておけば, あとはそれを (n!)/2 倍することとで答えが得られることを抑えておきます。これは, 長さ n の順列が n! 通りあり, そのうち例えば 0-1-2 と 2-1-0 などは結局並び方が逆なだけで line としては同じなので 半分になることからわかります。

ということで, 0-1-...-(n-1) という長さ n の line が, 各グラフに現れる数を求めれば良いです。

dp[n][l] = (n 頂点からなるグラフで, MST の辺の最高コストが l 以下となるようなグラフの数) とします。

すると, dp[n][l] は以下の値の和です。

まず, l 以下ということは l-1 以下のものは当然含まれるので dp[n][l-1]

あとは MST の辺の最高コストが l になるものです。
i-1 番目と i 番目の頂点の間の辺のコストが初めてコスト l の辺になるとすると, その辺が出てくる前の頂点 i 個での MST の辺の最高コストは l-1 以下で, それより後に出てくる頂点 n-i 個の MST の辺の最高コストは l 以下になります。
それぞれの場合の数は dp[i][l-1], dp[n-i][l] ですね。

また, この i 個の頂点群と n-i 個の頂点群を結ぶ辺は, i-1 と i を結ぶ辺はコストが l で確定ですが, それ以外の辺は l 以上 L 以下なら何でも良いので (L-l+1)^(i*(n-i)-1) 通りあります。

まとめると, MST の辺の最高コストが l になるもののうち, i-1 番目と i 番目の頂点の間の辺のコストが初めてコスト l の辺になるようなものは, dp[i][l-1] * dp[n-i][l] * (L-l+1)^(i*(n-i)-1) 通りあります。

この i を i = 1 〜 n-1 まで走らせれば良いです。

得た知見
  • dp の引数として「〜以下になるやつ」みたいなのは計算量削減でよく使うけどこの解法だとそれじゃないと解けない感じで面白い
  • dp の考え方でコストが l に「初めて」なる場所で場合分け, という考え方は全くなかったのでなるほどと思った
const int MAXN = 222;
const ll MOD = 1e9+7;

ll dp[MAXN][MAXN];
int L;

ll mod_pow(ll x, ll p) {
    if (x == 0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p%2) return x*mod_pow(x, p-1)%MOD;
    ll tmp = mod_pow(x, p/2);
    return tmp*tmp%MOD;
}

ll dfs(int n, int l) {
    if (n == 1) return 1;
    if (l == 0) return 0;
    ll& ret = dp[n][l];
    if (ret == -1) {
        ret = dfs(n, l-1);
        for (int i = 1; i < n; i++) {
            ret += (dfs(i, l-1) * dfs(n-i, l) % MOD) * mod_pow(L-l+1, i*(n-i)-1) % MOD;
        }
        ret %= MOD;
    }
    return ret;
}

class LineMST {
public:
    int count(int N, int L) {
        memset(dp, -1, sizeof(dp));
        ::L = L;
        ll plus = 1;
        for (int i = 3; i <= N; i++) (plus *= i) %= MOD;
        return dfs(N, L) * plus % MOD;
    }
};