結構いろんな考え方のできる問題!
問題概要
頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。
- 自己ループを持たない
- すべての頂点の次数が 2 以下である
- 各連結成分のサイズを並べたとき、その最大値がちょうど L である
制約
考えたこと
まず、自己ループを持たず、すべての頂点の次数が 2 以下であるとは、以下と同値になる。
- 連結成分がすべて「パス」か「サイクル」で構成される
- 多重辺はアリなので、サイズ 2 のサイクルはアリなことに注意
ざっくり次のような DP でできそう
- dp[ n ][ m ] := 頂点のうち 個を用いて、 本の辺が張られた状態にするような方法の個数
あとは、このような DP の具体的な方法と、「連結成分の最大サイズが 」という条件の扱い方について考えていく。
解法 (1):「サイズ L 以下」から「サイズ L-1 以下」を引く
最大サイズがちょうど であるものを数え上げるためには、「最大サイズが 以下である個数」から「最大サイズが 以下である個数」を引くという定石がある。ここでは「最大サイズが 以下」という条件で考えることにする。
dp は、一見次のようにすればよさそうに見える。つまり、dp[ n ][ p ] からの遷移は「残りの 個から () 個を選んでパスまたはサイクルを形成する」ことによって実現できそうである。
- dp[ n + k ][ m + k - 1 ] += dp[ n ][ m ] × C(N - n, k) × (サイズ k のパスの個数)
- dp[ n + k ][ m + k ] += dp[ n ][ m ] × C(N - n, k) × (サイズ k のサイクルの個数)
しかしこのままではダブルカウントがある。たとえば、 のとき
- 先にサイズ 3 のパス (1-2-3) を作り、その後サイズ 3 のパス (4-5-6) を作る
- 先にサイズ 3 のパス (4-5-6) を作り、その後サイズ 3 のパス (1-2-3) を作る
という場合をダブルカウントしてしまう。これを防ぐためには
残りの要素から新たにいくつかの要素を選ぶときに、添字が最小のものはかならず選ぶ
というふうにする方法がある (他の方法もある)。よって、DP を次のように修正すれば OK。
- dp[ n + k ][ m + k - 1 ] += dp[ n ][ m ] × C(N - n - 1, k - 1) × (サイズ k のパスの個数)
- dp[ n + k ][ m + k ] += dp[ n ][ m ] × C(N - n - 1, k - 1) × (サイズ k のサイクルの個数)
最後に、サイズ k のパスの個数は k! / 2 個 (k = 1 のときは 1 個)、サイズ k のサイクルの個数は (k-1)! / 2 個 (k = 2 のときは 1 個) となる。サイズ k のサイクルの個数を求めるときに、円順列 (k-1)! を 2 で割るのは、ひっくり返して一致するものも同一視するため。
コード
全体として計算量は となる。
#include <bits/stdc++.h> using namespace std; // modint template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() const { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept { if (n == 0) return 1; if (n < 0) return modpow(modinv(r), -n); auto t = modpow(r, n / 2); t = t * t; if (n & 1) t = t * r; return t; } friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } return Fp<MOD>(u); } }; const int MOD = 1000000007; using mint = Fp<MOD>; // Binomial coefficient template<class T> struct BiCoef { vector<T> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].getmod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; mint solve(int N, int M, int L, const BiCoef<mint> &bc) { mint ivtwo = modinv(mint(2)); auto pathnum = [&](int n) { if (n == 1) return mint(1); else return bc.fact(n) * ivtwo; }; auto cyclenum = [&](int n) { if (n == 2) return mint(1); else return bc.fact(n-1) * ivtwo; }; vector<vector<mint>> dp(N+1, vector<mint>(M+1, 0)); dp[0][0] = 1; for (int i = 0; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (dp[i][j] == 0) continue; // add path for (int k = 1; k <= L && i+k <= N && j+k-1 <= M; ++k) { dp[i+k][j+k-1] += dp[i][j] * bc.com(N-i-1, k-1) * pathnum(k); } // add cycle for (int k = 2; k <= L && i+k <= N && j+k <= M; ++k) { dp[i+k][j+k] += dp[i][j] * bc.com(N-i-1, k-1) * cyclenum(k); } } } return dp[N][M]; } int main() { BiCoef<mint> bc(110000); int N, M, L; cin >> N >> M >> L; cout << solve(N, M, L, bc) - solve(N, M, L-1, bc) << endl; }
解法 (2):サイズ L を作ったかどうかフラグを持たせる
連結成分の最大サイズが という条件は、
- どの連結成分のサイズも 以下とする
- すでにサイズ の連結成分を作ったかどうかを DP のフラグにもたせる
という方法も考えられる。
解法 (3):サイズごとに考えていく
また、「単純に DP をするとダブルカウントが発生する」という部分については、サイズの昇順に DP する手もある。
- dp[ k ][ n ][ m ] := サイズ k 以下の連結成分のみを用いて、n 個の頂点を採用し、m 辺を形成した状態にする方法の個数
このようにするのは、「 人のメンバーをグループ分けするときに、人数が異なるグループ分けは区別できるが、人数が同一になるグループ分けは区別できない」という性質を利用している。一般に 人を 人グループ 組に分ける方法の個数は 通り (f(k, a) とおく) となる。
- dp[ k ][ i + ka ][ j + (k-1)a ] += dp[ k - 1 ][ i ][ j ] × C(N - i, ka) × f(k, a) × pow(サイズ k のパスの本数, a)
という感じの遷移をする (サイクルについても)。計算量は一見 になりそうだけど、調和級数の和のような感じになっていて となる。
コード
#include <bits/stdc++.h> using namespace std; // modint template<int MOD> struct Fp { long long val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() const { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept { if (n == 0) return 1; if (n < 0) return modpow(modinv(r), -n); auto t = modpow(r, n / 2); t = t * t; if (n & 1) t = t * r; return t; } friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } return Fp<MOD>(u); } }; const int MOD = 1000000007; //const int MOD = 998244353; using mint = Fp<MOD>; // Binomial coefficient template<class T> struct BiCoef { vector<T> fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].getmod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; mint solve(int N, int M, int L, const BiCoef<mint> &bc) { mint ivtwo = modinv(mint(2)); auto pathnum = [&](int n) { if (n == 1) return mint(1); else return bc.fact(n) * ivtwo; }; auto cyclenum = [&](int n) { if (n == 2) return mint(1); else return bc.fact(n-1) * ivtwo; }; mint resL, resL1; vector<vector<mint>> dp(N+1, vector<mint>(M+1, 0)), ndp = dp; dp[0][0] = 1; for (int k = 1; k <= L; ++k) { // add path ndp.assign(N+1, vector<mint>(M+1, 0)); for (int i = 0; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (dp[i][j] == 0) continue; for (int a = 0; i+a*k <= N && j+a*(k-1) <= M; ++a) { ndp[i+a*k][j+a*(k-1)] += dp[i][j] * bc.com(N-i, a*k) * bc.fact(a*k) * modpow(bc.finv(k) * pathnum(k), a) * bc.finv(a); } } } swap(dp, ndp); // add cycle if (k > 1) { ndp.assign(N+1, vector<mint>(M+1, 0)); for (int i = 0; i <= N; ++i) { for (int j = 0; j <= M; ++j) { if (dp[i][j] == 0) continue; for (int a = 0; i+a*k <= N && j+a*k <= M; ++a) { ndp[i+a*k][j+a*k] += dp[i][j] * bc.com(N-i, a*k) * bc.fact(a*k) * modpow(bc.finv(k) * cyclenum(k), a) * bc.finv(a); } } } swap(dp, ndp); } if (k == L) resL = dp[N][M]; else if (k == L-1) resL1 = dp[N][M]; } return resL - resL1; } int main() { BiCoef<mint> bc(110000); int N, M, L; cin >> N >> M >> L; cout << solve(N, M, L, bc) << endl; }