思路与算法

若最短路至少n-1且可达，则它恰为一条覆盖全部顶点的Hamilton路径，按距离给出唯一层序，内部顶点有(n-2)!种排列。沿该序，所有回边、自环及前进一层的边可以存在，其他前跳边不允许；共K=n(n+3)/2-1类边，其中n-1类相邻前进边至少各一条。剩余m-n+1条作为可重复选边，方案C(K+m-n,K-1)乘内部排列数。

正确性说明

最短路是简单路径，长度至多n-1；达到下界时所有顶点出现在该路径并且距离层号唯一，否则会产生更短路线。合法边只能不增加超过一层，且每一相邻前进类必须存在，反之这些条件保证最短距离恰n-1。平行边只计重数，扣除必需边后由插板法一一计数，无边排列重计。

复杂度

只取组合数较小侧m-n+1，阶乘积和逆元快速幂O(m+n+logMOD)时间，O(1)辅助空间；初始化常数。组合上参数小于MOD=1e9+7。

易错点

n=1只有一种自环重数图，单独输出1。m<n-1输出0。样例明确不可达图不计入，平行边也不额外编号；不要按m条有序编号边去计算。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1000000007;
ll power(ll a, ll b) {
    ll z = 1;
    for (; b; b /= 2, a = a * a % P)
        if (b & 1)
            z = z * a % P;
    return z;
}
int main() {
    ll n, m;
    cin >> n >> m;
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    if (m < n - 1) {
        cout << 0 << '\n';
        return 0;
    }
    ll k = m - n + 1, K = n * (n + 3) / 2 - 1, num = 1, den = 1;
    for (ll i = 1; i <= k; i++) {
        num = num * ((K + i - 1) % P) % P;
        den = den * i % P;
    }
    ll ans = num * power(den, P - 2) % P;
    for (ll i = 2; i <= n - 2; i++)
        ans = ans * i % P;
    cout << ans << '\n';
}