description
求 \(n\) 个点 \(m\) 条边的简单无向图（可以不连通）满足加入非负整数条边后可以变成 \(n\) 个点的环的个数。
要求线性复杂度。
- \(n\ge 3\)
solution
当 \(m>n\) 时，答案为 \(0\)。
当 \(m=n\) 时，相当于问 \(n\) 个点构成一个环的方案数，为 \(\dfrac{(n-1)!}{2}\)。
考虑当 \(m<n\) 的情况。
这时候的无向图一定是 \(k=n-m\) 条互不联通的链。我们不妨先把这些链看成是有序的，最后除以 \(k!\) 即可。
如果我们知道了每种大小的链有多少种方案，求出原答案就是一个有标号计数问题了，这让我们联想到指数生成函数。
设 \(g_{i}\) 表示大小（即点数）为 \(i\) 的有标号非空链的数量，有以下关系式：
-
\(g_{1}=1,g_{0}=0\)
-
\(g_{i}=\dfrac{i!}{2},i\ge 2\)
第一个式子是容易看出的，第二个式子是因为链不应该考虑正着放还是反着放，所以要阶乘除以 2。
我们写出 \(g\) 的指数生成函数 \(G(x)=\sum\limits_{i\ge 1} \dfrac{g_i}{i!} x^i=x+\dfrac{1}{2}x^2+\dfrac{1}{2}x^3\dots\)
把它推成封闭形式：
-
\(xG(x)=x^2+\dfrac{1}{2}x^3+\dfrac{1}{2}x^4+\dots\)
-
\((x-1)G(x)=\dfrac{1}{2}x^2-x\)
-
\(G(x)=\dfrac{x}{2}\cdot\dfrac{x-2}{x-1}\)
我们要求 \(k\) 条链拼起来，总点数为 \(n\) 的方案数，就是求 \([x^n]G(x)^k\)。
来推 \(G(x)^k\) ！
乘积的几部分分别 \(k\) 次方，有 \(G(x)^k=\dfrac{x^k}{2^k}\cdot (\dfrac{1}{x-1})^k \cdot (x-2)^k\)。
第一部分很好处理，第二部分 \((\dfrac{1}{x-1})^k=(1+x+x^2+x^3+\dots)^k\)，其第 \(t\) 项就是把 \(t\) 分成 \(k\) 个有序非负整数的方案数，使用插板法可知方案数是 \(\dbinom{t+k-1}{k-1}\)，最后一部分二项式展开就可以了。
于是我们可以写出 \([x^n]G(x)^k=\dfrac{1}{2^k}\sum\limits_{i=0}^{n-k}\dbinom{n-i-1}{k-1}\dbinom{k}{i}2^i(-1)^{k-i}\)
可以线性求出。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
using E=long long;
using ui=uint32_t;
using lint=__int128;
constexpr E inf=1e16,mod=1e9+7;
namespace Comb{
vector<E> fac(1,1ll),ifac(1,1ll),INV(2,1ll),pw;
inline E ksm(E a,E b,const E MOD=mod){
E ret=1;
assert(b>=0);
while(b){
if(b&1) ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int _n;
void CombPrework(int n){
pw.resize(n+1);
pw[0]=1;
for(int i=1; i<=n; i++) pw[i]=pw[i-1]*2%mod;
_n=n;
for(int i=2; i<=n; i++) INV.emplace_back((mod-mod/i)*INV[mod%i]%mod);
fac.resize(n+1),ifac.resize(n+1);
fac[0]=ifac[0]=1;
for(int i=1; i<=n; i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=ksm(fac[n],mod-2);
for(int i=n-1; i; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}
E Inv(E x){ return x<=_n?INV[x]:(x==1?1:Inv(mod%x)*(mod-mod/x)%mod); }
inline E C(E n,E m){
if(n<0||m<0||n<m) return 0;
while(fac.size()<=n){
fac.emplace_back(fac.back()*(fac.size())%mod);
ifac.emplace_back(ifac.back()*ksm(ifac.size(),mod-2)%mod);
}
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline E A(E n,E m){
if(m<0) return 0;
return C(n,m)*fac[m]%mod;
}
};
using namespace Comb;
void solve(){
E n,m;
cin>>n>>m;
if(n==m){
cout<<fac[n]*ksm(2*n,mod-2)%mod<<'\n';
return ;
}
E k=n-m;
if(k<0){
cout<<0<<'\n';
return ;
}
E ans=0;
for(E i=0; i<=m; i++){
E x=C(m-i+k-1,k-1)*C(k,i)%mod;
if(k-i>=0) x=x*pw[k-i]%mod;
else x=0;
if(i&1) ans=(ans-x+mod)%mod;
else ans=(ans+x)%mod;
}
ans=ans*ksm(pw[k],mod-2)%mod*fac[n]%mod*ifac[k]%mod;
cout<<(ans%mod+mod)%mod<<'\n';
}
signed main(){
cout.tie(nullptr),cin.tie(nullptr)->sync_with_stdio(false);
CombPrework(5e5);
int T;
cin>>T;
while(T--) solve();
return 0;
}