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
形式化题目
有向图
要求:从
约束:
关于"至少
"的解读。 一条从 到 的简单路径最多含 条边, 所以只要 可达,最短路长度就 。 于是"最短路 且可达"等价于"最短路恰好等于 "。 输入样例 输出 ,与这个解读一致(见下文推导)。
正解
思路
第一步:看清最短路的形状。
记
它是汉密尔顿路径。更关键的是:沿最短路
第二步:固定链之后,哪些边能加、哪些边不能加。
固定顶点顺序
| 类型 | 条件 | 可否存在 | 原因 |
|---|---|---|---|
| 链边 | 必须 |
否则这条长为 |
|
| 捷径边 | 必须 |
有它就能从 |
|
| 反向边 / 自环 | 任意条数 | 只会往回走或原地停留,绝不缩短正向最短路 |
第 3 类(含自环)恰好是所有满足
第 2 类捷径边共
第三步:不同排列互不重叠,所以不用容斥。
若两个不同的中间顶点排列
第四步:隔板法。
固定一条链的
条边要投到
最终答案
边界:
:起点即终点, 自动成立; 条边只能全是自环 ,图唯一,答案 。 且 :凑不齐 条链边,无解,答案 。 : , , 。对 得 , 与样例一致。直接枚举也对得上: 、 、 ,非负解共 组。 的退化情形:此时 ,答案就是 。 真实数据点 5 给出 ,正是这一分支(唯一链 ,无余边)。
代码
#!/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()// 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;
}复杂度
- 时间:
。阶乘 ,组合数逐因子 ,快速幂求逆元 。 顶格 时只有约 次模乘。 - 空间:
存一张阶乘表(Python 版为 )。
总结
本题的全部难度在第 1 步的观察:在"最短路长为 long long 计算。
数据说明。 本题素材源(
new_ROJ/problems/1813/)自带数据生成脚本data.py, 10 个测试点由该脚本按题面分层(边界 // / 过渡 / 双顶格)生成, 因此数据是自造的、并非官方原题数据;题面本身与网络上的同源题 JZOJ 3085【NOIP2012模拟11.3】图的计数逐字一致,公式亦与多处公开题解吻合。 本解已对该 个真实点逐点比对通过。