题意

给定正整数 $n,m$，求 $n$ 个点的没有自环和重边的有标号有向图 $G$ 的个数，使得 $G$ 中每个点在至多一个环上，且不在任意一个环上的边的数量恰好为 $m$。答案对 $10^9+9$ 取模。

题解

考虑有标号 DAG 计数:

设 $n$ 个点的答案为 $f_n$，则

$$ f_n=\sum_{i\ge 1}\left(-1\right)^{i-1}\binom{n}{i}2^{i\left(n-i\right)}f_{n-i} $$

同理，对于本题，设 $n$ 个点，$m$ 条边的方案数为 $g_{n,m}$。令 $G_{n}\left(w\right)=\sum_{i\ge 0}g_{n,i}w^i$，则 $G_n\left(w\right)$ 满足:

$$ G_{n}\left(w\right)=\sum_{i\ge 1}\binom{n}{i}\sum_{j}\begin{bmatrix}i\\j\end{bmatrix}\left(-1\right)^{j-1}\left(1+w\right)^{i\left(n-i\right)}G_{n-i}\left(w\right) $$

而 $\sum_{i}\begin{bmatrix}n\\i\end{bmatrix}\left(-1\right)^{i-1}=\left(-1\right)\times \left(-1\right)^{\overline{n}}$，在 $n\ge 2$ 时均为 $0$

所以 $G_n\left(w\right)=n!\left(1+w\right)^{n\left(n-1\right)/2}$，线性求组合数即可。

Code

#include <iostream>
#include <algorithm>
constexpr int p(1e9+9),N(1e6+10);
using ll=long long;
int main()
{
    int n,m;std::cin>>n>>m;
    static int inv[N];inv[1]=1;for(int i(2);i<=m;++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;
    ll k(1ll*n*(n-1)/2);
    k%=p;
    int ans(0);
    if(k>=m)
    {
        ans=1;
        for(int i(1);i<=m;++i) ans=1ll*(k-i+1)*inv[i]%p*ans%p;
        for(int i(1);i<=n;++i) ans=1ll*ans*i%p;
    }
    std::cout<<ans<<std::endl;
    return 0;
}