2022-12-13

AtCoder ABC 281 G - Farthest City (黄色, 600 点)

残り 1 分でなんとか通せた。

問題へのリンク

問題概要

頂点数 $N$ の連結な単純無向グラフ (頂点番号は $1, 2, \dots, N)$ であって、次の条件を満たすものの個数を $M$ で割ったあまりを求めよ。

$d_{N} \gt d_{2}$
$d_{N} \gt d_{3}$
$\dots$
$d_{N} \gt d_{N-1}$

なお、ここで、頂点 $1$ から各頂点 $2, 3, \dots, N$ までの最短距離を $d_{2}, d_{3}, \dots, d_{N}$ としている。

制約

$3 \le N \le 500$
$10^{8} \le M \le 10^{9}$

考えたこと

グラフの個数を数える系の問題はやっぱり難しい！

最初は、頂点 $d_{N}$ の値で場合分けすることを考えた。 $M = d_{N}$ のとき、のこりの $N-2$ 個の頂点のうちのいくつかは $d$ 値が $M-1$ になるはずだ。そうやっていくと、再帰的に求められそうな雰囲気を感じた。

そこで、次の再帰関数を考えた。元の問題と異なり、始点を $n$ としている。

$f(n, m, a)$ ← $n$ 頂点のグラフを考える。頂点 $n$ から頂点 $1, 2, \dots, n-1$ への最短距離を $d_{1}, d_{2}, \dots, d_{n-1}$ としたとき、

$d_{1} = m$
$d_{2} = m$
$\dots$
$d_{a} = m$
$d_{a+1} \lt m$
$d_{a+2} \lt m$
$\dots$
$d_{n-1} \lt m$

が成り立つようなものの個数

つまり、最短距離が $m$ となる頂点がちょうど $a$ 個あるようなものの個数を考えるのだ。答えは $\displaystyle \sum_{m=1}^{N-1} f(N, m, 1)$ と表せる。

本番はこのまま考察を進めていったが、このままだと $O(N^{4})$ の解法となる。しかし自分が作った DP の遷移式を見ると、実は $m$ の値に依存しないことに気づいた。つまり、上の関数の定義から $m$ を削って良い！！

整理して、次の関数を求める。

$f(n, a)$ ← $n$ 頂点のグラフを考える。頂点 $n$ から頂点 $1, 2, \dots, n-1$ への最短距離を $d_{1}, d_{2}, \dots, d_{n-1}$ とする。また $d_{1} = m$ とおく

$d_{1} = d_{2} = \dots = d_{a} = m$
$d_{a+1} \lt m$
$d_{a+2} \lt m$
$\dots$
$d_{n-1} \lt m$

が成り立つようなものの個数

遷移を詰める

頂点 $a+1, a+2, \dots, n-1$ のうち、最短距離が $m-1$ であるものの個数 $k$ で場合分けする。

このとき、求めるグラフは次の性質を満たす。ここで、頂点 $1, 2, \dots, a$ をグループ P、残りの頂点のうち最短距離が $m-1$ である $k$ 個の頂点をグループ Q、それ以外をグループ R と呼んでいる。

グループ P の各頂点 $v$ に対して、グループ Q の頂点 $r$ が少なくとも 1 つ存在して、辺 $(u, v)$ が貼られている
グループ P の頂点とグループ R の頂点との間に辺はない

これを踏まえて、数え上げる。

グループ P 同士の辺について： $\displaystyle 2^{{}_{a}\mathrm{C}_{2}}$ 通り
グループ P とグループ Q(, R) の間の辺について： $(2^{k}-1)^{a}$ 通り
グループ Q, R 同士の辺について： ${}_{n-a-1}\mathrm{C}_{k} \times f(n-a, k)$ 通り

よって、

$f(n, a) = \displaystyle \sum_{k=1}^{n-2} 2^{{}_{a}\mathrm{C}_{2}} {}_{n-a-1}\mathrm{C}_{k} (2^{k}-1)^{a} f(n-a, k)$

となります。これを DP として実装すると $O(N^{3})$ の計算量となる。

コード

#include <bits/stdc++.h>
using namespace std;

// mod
int MOD;

// 二項係数
const int MAX_C = 1000;
long long Com[MAX_C][MAX_C];
void COMinit() {
    Com[0][0] = 1;
    for (int i = 1; i < MAX_C; ++i) Com[0][i] = 0;
    for (int i = 1; i < MAX_C; ++i) {
        Com[i][0] = 1;
        for (int j = 1; j < MAX_C; ++j) {
            Com[i][j] = (Com[i-1][j-1] + Com[i-1][j]) % MOD;
        }
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return Com[n][k];
}

// two[k]：2^k、coef[k][a]：(2^k-1)^a
vector<long long> two;
vector<vector<long long>> coef;

// DP
vector<vector<long long>> dp;
long long func(int n, int a) {
    if (n == 1) return (a == 0);
    if (a == 0) return (n == 1);
    if (dp[n][a] != -1) return dp[n][a];

    long long res = 0;
    for (int k = 0; k <= n-a-1; ++k) {
        long long cur = func(n-a, k);
        cur = cur * two[a*(a-1) / 2] % MOD;
        cur = cur * Com[n-a-1][k] % MOD;
        cur = cur * coef[k][a] % MOD;
        res = (res + cur) % MOD;
    }
    return dp[n][a] = res;
}

int main() {
    // 入力
    int N;
    cin >> N >> MOD;
    
    // 二項係数などの準備
    COMinit();
    two.assign(N * N + 1, 1);
    for (int k = 0; k < N * N; ++k) two[k + 1] = two[k] * 2 % MOD;
    coef.assign(N + 1, vector<long long>(N + 1, 1));
    for (int k = 1; k <= N; ++k) {
        long long base = (two[k] + MOD - 1) % MOD;
        for (int a = 1; a <= N; ++a) {
            coef[k][a] = coef[k][a-1] * base % MOD;
        }
    }

    // DP
    dp.assign(N + 1, vector<long long>(N + 1, -1));
    cout << func(N, 1) << endl;
}

形式的冪級数

を使う解法があるらしい。いずれちゃんと理解したい

→ 高速化 by yuto1115

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 281 G - Farthest City (黄色, 600 点)

問題概要

制約

考えたこと

遷移を詰める

コード

形式的冪級数