[数学记录]CF1109D Sasha and Interesting Fact from Graph Theory
command_block
2020-10-31 13:31:58
**题意** : 给定参数 $n,m,a,b$。
求有多少种 $n$ 个点的有标号无根树，满足下列条件 :
- 边权值域为 $[1,m]∩Z$。
- 节点 $a,b$ 之间的路径长度恰为 $m$。
答案对 $10^9+7$ 取模。
$n,m\leq 10^6,a≠b$ ,时限$\texttt{2.5s}$。
------------
显然 $a,b$ 对答案无影响。
考虑枚举 $a,b$ 路径之间的点数 (不包括 $a,b$) ，构造出路径，再考虑其余的部分。
${\rm Ans}=\sum\limits_{i=0}^n\dbinom{n-2}{i}i!\dbinom{m-1}{i}f(i+2)m^{n-i-2}$
其中，$\dbinom{n-2}{i}$ 是选出 $i$ 个编号的方案数。
$i!$ 是 $i$ 个点任意排列的方案数。
$\dbinom{m-1}{i}$ 是 $i+1$ 条边和为 $m$ 的方案数。
$f(k)$ 是一条长度为 $k$ 的链和剩余的 $n-k$ 个点能够组成的生成树个数。
结论 ： $f(k)=kn^{n-k-1}$
推导方法可见 [[数学记录]P5206 [WC2019] 数树](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p5206-wc2019-shuo-shu)
$m^{n-i+2}$ 是剩余 $n-i+2$ 条边的权值方案数。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 1005000
#define ll long long
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
int n,m;
ll f(int k)
{return k*powM(n,mod+n-k-2)%mod;}
int main()
{
scanf("%d%d",&n,&m);
Init(max(n,m));
ll ans=0;
for (int i=0;i<=min(n-2,m-1);i++)
ans=(ans+C(n-2,i)*C(m-1,i)%mod*fac[i]%mod*f(i+2)%mod*powM(m,n-i-2))%mod;
printf("%lld\n",ans);
return 0;
}
```