图的计数

GitHub跳转原题关系图返回列表

1 到 n 最短路为 n-1 时必经全部点,链固定后只禁 C(n-1,2) 条捷径边,答案 = (n-2)!·C(n²-(n-1)(n-2)/2+m-n, m-n+1)。

OJ: roj

题目 ID: 1813

难度:提高+/省选-

标签:数学组合数学计数python

创建: 2026-10-08 06:12

更新: 2026-10-08 06:12

形式化题目

有向图 GG 的顶点集固定为 V={1,2,…,n}V = \{1, 2, \dots, n\},允许重边与自环, 边的条数恰好是 mm。一张图由它的边重数矩阵 (cu,v)u,v∈V(c_{u,v})_{u,v \in V}(cu,v⩾0c_{u,v} \geqslant 0, ∑cu,v=m\sum c_{u,v} = m)唯一确定,于是计数等价于数"这样的非负整数矩阵有多少个"。

要求:从 11 号点走到 nn 号点的最短路径长度(边数)至少为 n−1n - 1。求方案数  mod 109+7\bmod 10^9+7。

约束:

1⩽n⩽10000,1⩽m⩽50000. 1 \leqslant n \leqslant 10000, \qquad 1 \leqslant m \leqslant 50000 .

关于"至少 n−1n-1"的解读。 一条从 11 到 nn 的简单路径最多含 n−1n-1 条边, 所以只要 1⇝n1 \rightsquigarrow n 可达,最短路长度就 ⩽n−1\leqslant n-1。 于是"最短路 ⩾n−1\geqslant n-1 且可达"等价于"最短路恰好等于 n−1n-1"。 输入样例 n=2,m=2n=2,m=2 输出 44,与这个解读一致(见下文推导)。

正解

思路

第一步:看清最短路的形状。

记 d(v)d(v) 为 11 到 vv 的最短路长度。若 d(n)=n−1d(n) = n-1,考虑这条最短路上顶点出现的顺序, 它一定是一条经过全部 nn 个点的路径(n−1n-1 条边最多覆盖 nn 个点, 而只覆盖 n−1n-1 个点的路径最多 n−2n-2 条边,够不到 n−1n-1)。把这条顶点序列记作

u0=1→u1→u2→⋯→un−1=n. u_0 = 1 \to u_1 \to u_2 \to \cdots \to u_{n-1} = n .

它是汉密尔顿路径。更关键的是:沿最短路 d(ui)=id(u_i) = i 恰好成立(每步最多使距离 +1+1, n−1n-1 步要从 00 涨到 n−1n-1,必须步步 +1+1)。因此中间顶点 u1,…,un−2u_1, \dots, u_{n-2} 是 {2,…,n−1}\{2, \dots, n-1\} 的某个排列,排列唯一地决定了这条链。

第二步:固定链之后,哪些边能加、哪些边不能加。

固定顶点顺序 u0,u1,…,un−1u_0, u_1, \dots, u_{n-1},图中的有向边分三类:

类型 条件 可否存在 原因
链边 ui→ui+1u_i \to u_{i+1} 必须 ⩾1\geqslant 1 条 否则这条长为 n−1n-1 的路不通
捷径边 ui→uj, j⩾i+2u_i \to u_j,\ j \geqslant i+2 必须 00 条 有它就能从 uiu_i 直跳 uju_j,把 d(uj)d(u_j) 压到 ⩽i+1<j\leqslant i+1 < j
反向边 / 自环 ui→uj, i⩾ju_i \to u_j,\ i \geqslant j 任意条数 只会往回走或原地停留,绝不缩短正向最短路

第 3 类(含自环)恰好是所有满足 i⩾ji \geqslant j 的下标对,个数为

1+2+⋯+n=n(n+1)2. 1 + 2 + \cdots + n = \frac{n(n+1)}{2} .

第 2 类捷径边共 (n−12)=(n−1)(n−2)2\binom{n-1}{2} = \dfrac{(n-1)(n-2)}{2} 种(在下标 0..n−10..n-1 里挑 j⩾i+2j \geqslant i+2 的对), 它们被全部禁掉。链边 n−1n-1 种。于是允许出现的边类型总数

A=(n−1)+n(n+1)2=n2+3n−22=n2−(n−12). A = (n-1) + \frac{n(n+1)}{2} = \frac{n^2 + 3n - 2}{2} = n^2 - \binom{n-1}{2} .

第三步:不同排列互不重叠,所以不用容斥。

若两个不同的中间顶点排列 p≠qp \neq q,取它们第一个不同的位置 tt(1⩽t⩽n−21 \leqslant t \leqslant n-2), pp 的链边 ut−1→utu_{t-1} \to u_t 在 qq 的定义下就是一条捷径边(qq 的链要继续走别的中间点, 这个边跨越了至少一个下标),反之亦然。于是 pp 允许的图在 qq 里被禁、qq 允许的图在 pp 里被禁, 两个图族严格互斥。中间点排列数为 (n−2)!(n-2)!,直接把每个排列的合法图数相加即可。

第四步:隔板法。

固定一条链的 n−1n-1 条边各先放 11 条,用掉 n−1n-1 条,还剩

k=m−(n−1)=m−n+1 k = m - (n - 1) = m - n + 1

条边要投到 AA 种允许类型里(每种可放 00 条、可重复放)。由可重组合:

(A+k−1k)=(A+m−nm−n+1). \binom{A + k - 1}{k} = \binom{A + m - n}{m - n + 1} .

最终答案

 Ans=(n−2)!⋅( A+m−n  m−n+1 ) mod (109+7),A=n2+3n−22  \boxed{\ \text{Ans} = (n-2)! \cdot \binom{\,A + m - n\,}{\,m - n + 1\,} \bmod (10^9+7),\qquad A = \frac{n^2+3n-2}{2}\ }

边界:

  • n=1n = 1:起点即终点,d=0=n−1d = 0 = n-1 自动成立;mm 条边只能全是自环 1→11 \to 1,图唯一,答案 11。
  • n⩾2n \geqslant 2 且 m<n−1m < n-1:凑不齐 n−1n-1 条链边,无解,答案 00。
  • n=2n = 2:0!=10! = 1,A=22−(12)=4A = 2^2 - \binom{1}{2} = 4,k=m−1k = m - 1。对 m=2m = 2 得 1⋅(5−11)=41 \cdot \binom{5-1}{1} = 4, 与样例一致。直接枚举也对得上:c1,2⩾1c_{1,2} \geqslant 1、c1,1+c2,2⩾0c_{1,1}+c_{2,2} \geqslant 0、 c1,2+c1,1+c2,2=2c_{1,2}+c_{1,1}+c_{2,2} = 2,非负解共 44 组。
  • k=0k = 0 的退化情形:此时 (A−10)=1\binom{A-1}{0} = 1,答案就是 (n−2)!(n-2)!。 真实数据点 5 给出 n=4,m=3⇒2=2!n=4,m=3 \Rightarrow 2 = 2!,正是这一分支(唯一链 1→2→3→41\to2\to3\to4,无余边)。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:12
# update_at: 2026-10-08 06:12

import sys

MOD = 10**9 + 7


def binom(n: int, k: int) -> int:
    """C(n, k) mod MOD:逐因子乘出分子与分母,再用费马小定理求分母的逆元。"""
    k = min(k, n - k)
    num = den = 1
    for i in range(k):
        num = num * (n - i) % MOD
        den = den * (i + 1) % MOD
    return num * pow(den, MOD - 2, MOD) % MOD


def count(n: int, m: int) -> int:
    """n 点 m 边、1 -> n 最短路长度恰为 n-1 的有向图个数(含重边自环)mod MOD。"""
    if n == 1:  # 起点即终点,m 条边只能全是自环,图唯一
        return 1
    if m < n - 1:  # 凑不齐 n-1 条链边,无解
        return 0

    fact = 1
    for i in range(2, n - 1):  # (n-2)!:链上的中间点可任意排列
        fact = fact * i % MOD

    kinds = n * n - (n - 1) * (n - 2) // 2  # 允许出现的边类型数 A
    free = m - n + 1  # 去掉每条链边的 1 条之后,可自由分配的边数
    return fact * binom(kinds + free - 1, free) % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    print(count(n, m))


if __name__ == "__main__":
    solve()
cpp
// 1813 图的计数
// 一本通·高手训练 六、数学基础  同源题:JZOJ 3085【NOIP2012模拟11.3】图的计数
//
// 题意:统计 n 个点、m 条边的有向图(允许重边、自环)的个数,要求 1 号点到 n 号点
//       的最短路径长度 >= n-1(有解时即恰好 = n-1),答案 mod 1e9+7。
//
// 关键结论(推导见 index.md):
//   设 1 = u_0 -> u_1 -> ... -> u_{n-1} = n 是一条长度为 n-1 的最短路,则它必经全部 n 个点。
//   固定这个顶点顺序后,允许的边类型只有:
//     · n-1 条链边 u_i -> u_{i+1}(每条至少 1 条,否则到不了 n)
//     · 全部反向边/自环(i >= j 的对),它们走回头路,绝不会缩短最短路
//   禁止的是 "捷径边" u_i -> u_j (j >= i+2),共 C(n-1,2) 种,会让最短路变短。
//   中间 n-2 个点可任意排列,故乘 (n-2)!;不同排列对应的图集互不相交,直接累加即可。
//   余下 k = m-n+1 条边自由投到 A = n^2 - C(n-1,2) = (n^2+3n-2)/2 种允许类型里,
//   隔板法(可重组合)给出 C(A+k-1, k)。
//
//   答案 = (n-2)! * C(A + m - n, m - n + 1)  (mod 1e9+7)
//   特判:n = 1 -> 1;m < n-1 (n >= 2) -> 0。
//
// 复杂度:O(n + m) 时间(阶乘 + k 个因子 + 一次快速幂),O(1) 空间。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;  // 1e9+7

// 题目规模不大,直接开全局数组存阶乘相关(本题其实只需常数网格)
const int MAXN = 10005;

ll fact[MAXN];  // fact[i] = i! mod MOD

// 快速幂:求 x^b mod MOD
ll power(ll x, ll b) {
    ll res = 1;
    x %= MOD;
    while (b > 0) {
        if (b & 1) res = res * x % MOD;
        x = x * x % MOD;
        b >>= 1;
    }
    return res;
}

// 组合数 C(N, K) mod MOD(本题 N < MOD,逐因子乘 + 费马小定理求逆元)
ll comb(ll N, ll K) {
    if (K < 0 || K > N) return 0;
    if (K > N - K) K = N - K;  // 取小的一侧,减少循环次数
    ll num = 1, den = 1;
    for (ll i = 0; i < K; i++) {
        num = num * ((N - i) % MOD) % MOD;  // 分子:N * (N-1) * ... * (N-K+1)
        den = den * ((i + 1) % MOD) % MOD;  // 分母:K!
    }
    return num * power(den, MOD - 2) % MOD;
}

int main() {
    ll n, m;
    if (scanf("%lld %lld", &n, &m) != 2) return 0;

    // 特判 1:n = 1,起点即终点,距离恒为 0 = n-1,m 条边只能全是自环 -> 唯一图
    if (n == 1) {
        printf("1\n");
        return 0;
    }

    // 特判 2:边不够连成 n 个点的链,无解
    if (m < n - 1) {
        printf("0\n");
        return 0;
    }

    // 阶乘:(n-2)!
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;

    // 允许的边类型数 A = n^2 - C(n-1, 2)
    ll A = n * n - (n - 1) * (n - 2) / 2;
    ll k = m - n + 1;  // 剩余自由分配的边数

    ll ans = fact[n - 2] * comb(A + k - 1, k) % MOD;
    printf("%lld\n", ans);
    return 0;
}

复杂度

  • 时间:O(n+m)O(n + m)。阶乘 O(n)O(n),组合数逐因子 O(k)⩽O(m)O(k) \leqslant O(m),快速幂求逆元 O(log⁡MOD)O(\log \text{MOD})。 顶格 n=10000,m=50000n = 10000, m = 50000 时只有约 6×1046 \times 10^4 次模乘。
  • 空间:O(n)O(n) 存一张阶乘表(Python 版为 O(1)O(1))。

总结

本题的全部难度在第 1 步的观察:在"最短路长为 n−1n-1"的约束下,最短路上距离值 0,1,…,n−10,1,\dots,n-1 各恰出现一次,于是顶点顺序被距离函数唯一确定,图的骨架被迫退化成一条 链 + 若干"回头边"。一旦看清这一点,剩下的就是最朴素的排列计数((n−2)!(n-2)!) 与隔板法((A+k−1k)\binom{A+k-1}{k}),不存在容斥或容错。实现上注意 m<n−1m < n-1 与 n=1n = 1 两个特判、以及 A+k−1A + k - 1 用 long long 计算。

数据说明。 本题素材源(new_ROJ/problems/1813/)自带数据生成脚本 data.py, 10 个测试点由该脚本按题面分层(边界 / 30%30\% / 60%60\% / 过渡 / 双顶格)生成, 因此数据是自造的、并非官方原题数据;题面本身与网络上的同源题 JZOJ 3085【NOIP2012模拟11.3】图的计数逐字一致,公式亦与多处公开题解吻合。 本解已对该 1010 个真实点逐点比对通过。