[数学记录]CF1109D Sasha and Interesting Fact from Graph Theory
command_block
·
·
个人记录
题意 : 给定参数 n,m,a,b。
求有多少种 n 个点的有标号无根树，满足下列条件 :
-
边权值域为 [1,m]∩Z。
-
节点 a,b 之间的路径长度恰为 m。
答案对 10^9+7 取模。
------------
显然 $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 个编号的方案数。
$\dbinom{m-1}{i}$ 是 $i+1$ 条边和为 $m$ 的方案数。
$f(k)$ 是一条长度为 $k$ 的链和剩余的 $n-k$ 个点能够组成的生成树个数。
结论 ： $f(k)=kn^{n-k-1}
推导方法可见 [数学记录]P5206 [WC2019] 数树
```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;
}
```