可以写其他OJ题解了，赶紧来整一份

题目描述

询问有多少个包含 $n$ 个点，$m$ 条边的有向图，从 $1$ 号点到达 $n$ 号点需要经过至少 $n − 1$ 条边。
该有向图中可以包含重边和自环。

输入

输入共一行，包含两个整数 $n,m$。

输出

输出共一行，仅一个整数表示答案。

由于答案可能很大，输出结果请对 $10^9+7$ 取模。

数据范围

对于 $30\%$ 的数据，$n \leq 5$，$m \leq 10$；

对于 $60\%$ 的数据，$n \leq 80$，$m \leq 3000$；

对于 $100\%$ 的数据，$1 \leq n \leq 10000$，$1 \leq m \leq 50000$。

输入样例

2 2

输出样例

4

样例解释

共有以下 $4$ 种符合题意的有向图：

• $1 \rightarrow 2, 1 \rightarrow 2$
• $1 \rightarrow 2, 2 \rightarrow 1$
• $1 \rightarrow 2, 2 \rightarrow 2$
• $1 \rightarrow 2, 1 \rightarrow 1$

思路

首先，考虑爆搜

首先，找性质，从 1 号点到达 n 号点需要经过至少 n − 1 条边的图等价于最短路径从一号点到 n 号点，将每个点遍历到且只遍历一次的图

证：

• 若最短路径中存在某个点没有遍历，那么必然存在至少一个点被遍历两次。
• 若最短路径中存在某个点被遍历两次及以上，则说明该路径存在环，与 其为最短路径 不符。

那么观察到这个性质之后，可以将 $n − 1$ 条边先分配给 $n$ 个点，形成一条链。
再考虑剩下 $m - n + 1$ 条边。

我们要将 $m - n + 1$ 条边加入链中，并且满足保证最短路不变。

直接算不好算，先算只加一条边。

根据容斥原理
合法的加入方案数 $=$ 总方案数 $−$ 不合法的方案数。

总方案数为 $n \times n = n ^ 2$，不符合法方案数即改变最短路长度的方案数，为 $C ^ 2 _ {n - 1} = \frac{(n - 1)(n - 2)}{2}$

那么我们就求出了只加一条边的合法方案数为 $n ^ 2 - \frac{(n - 1)(n - 2)}{2} = \frac{n ^ 2 + 3n - 2}{2}$。

接下来放剩下 $m - n + 1$ 条边，就可以看做一个非常经典的挡板问题

将 $A$ 个球放入 $B$ 个挡板中，方案数为 $C ^ A _ {A + B - 1}$

$m - n + 1$ 条边放入 $\frac{n ^ 2 + 3n - 2}{2}$ 个可选方案中，方案数为 $C ^ {m - n + 1} _ {m - n + 1 + \frac{n ^ 2 + 3n - 2}{2} - 1}$。

整理得 $C ^ {m - n + 1} _ {m + \frac{n(n + 1)}{2} - 1}$

由于要求从 $1$ 号点到 $n$ 号点，中间经过点顺序任意，所以还要乘上中间 $n - 2$ 个点的全排列方案数，即 $(n - 2)!$

最终答案为 $C ^ {m - n + 1} _ {m + \frac{n(n + 1)}{2} - 1}(n - 2)!$

需要取模，采用逆元即可。

时间复杂度分析

总时间复杂度瓶颈在求阶乘上。
由于求组合数时需要求出 $(m + \frac{n(n + 1)}{2} - 1)!$
所以总时间复杂度为平方级别。
具体时间复杂度较为玄学，不好分析。
看起来是 $O(n ^ 2 + m)$，但实际效果比这要好很多不然也过不去。
非常极限，需要常数上做一些优化。

C++ 代码

不优化代码 $80pts$

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;

const LL mod = 1000000007;
LL n, m;

LL fact(LL x)
{
    LL ans = 1;
    for (int i = 2; i <= x; i ++ )
        ans = ans * i % mod;
    return ans;
}

LL qmi(LL x,LL k)
{
    LL ans = 1;
    while (k)
    {
        if (k & 1) ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    LL k = (n * n + n >> 1) - 1;
    LL inv = qmi(fact(k - 1 + n) * fact(m - n + 1) % mod, mod - 2);
    cout << fact(n - 2) * fact(m + k) % mod * inv % mod;
    return 0;
}

我居然中间还在试用一个长度为1e8的long long数组存阶乘。。空间炸了。。不愧是我。。

由于只需要用到几个数的阶乘，存一下就好啦~
优化后代码 $100pts$

#include <stdio.h>

typedef long long LL;

int n, m;
LL MOD = 1000000007;

LL power(LL x, LL k)
{
    LL ans = 1;
    while (k)
    {
        if (k & 1) ans = ans * x % MOD;
        x = x * x % MOD;
        k >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d %d", &n, &m);
    if (m < n - 1)
    {
        putchar('0');
        return 0;
    }
    LL k = (n * n + n >> 1) - 1;
    LL t1, t2, t3, t4;
    t1 = t2 = t3 = t4 = 1;
    for (int i = 1; i <= m + k; i ++ )
    {
        t4 = t4 * i % MOD;
        if(i == k - 1 + n) t1 = t4;
        if(i == m - n + 1) t2 = t4;
        if(i == n - 2) t3 = t4;
    }
    LL inv = power(t1 * t2 % MOD, MOD - 2);
    printf("%lld",t3 * t4 % MOD * inv % MOD);
    return 0;
}