铬合金之声

Chrome VOX

「铬合金」是一张 $\it n$ 个结点的图 ${G = (V,E)}$ ，结点编号为 $1\dots n$ ，初始时不存在任何边。
请在其间连接 $\it m$ 条无向边使得这张图恰好存在 ${n-m}$ 个极大连通块。
一个方案的「声音」为所有极大连通块大小的乘积，求所有方案的「声音」之和，对 $10^9+7$ 取模。
一个连通块是一个点集 ${S \subseteq V}$ ，满足其中任意两个点可以互相到达。
一个极大连通块是一个点集 ${S \subseteq V}$ ，满足其中加入任意结点都不是连通块。
两种方案不同，当且仅当存在两个结点在一种方案中连边而在另一种方案中没有。

using namespace std; #include <bits/stdc++.h> #define M 10000005 #define ll long long #define mo 1000000007 ll qpow(ll x,ll y=mo-2){ ll r=1; for (;y;y>>=1,x=x*x%mo) if (y&1) r=r*x%mo; return r; } int n,m; int main(){ scanf("%d%d",&n,&m); ll pro=1; for (int i=1;i<=m;++i) pro=pro*i%mo; pro=qpow(pro); for (int i=n-m;i<=n-1;++i) pro=pro*i%mo; pro=pro*qpow(n,m)%mo; printf("%lld\n",pro); return 0; }

详情