OI - Sasha and Interesting Fact from Graph Theory(Codeforces)

事实是我还是不会做……


Part1. 题意

给出整数 $n,m,A,B$。

要求构造一棵 $n$ 个点(点的编号为 $1$~$n$)且带边权(边权均为正数)的树,要求 $A$ 到 $B$ 的路径上的边权之和恰好为 $m$。

求有多少种不同的构造方案。

=数据规模=

$1\leq n,m\leq10^6$


Part2. 题解

显然 A,B 到底取哪两个点根本不重要……

Part2/1. 组合数

我们枚举 A,B 之间的边数 i (i=1~n-1),当然因为每条边的边权至少为 1,所以 i≤m。

  • 然后我们就可以得到 A,B 之间的点数为 (i-1),于是要从除了 A,B 两点之外的 (n-2) 个点中选出 (i-1) 个点 —— $A_{n-2}^{i-1}$ ;
  • 而且 A,B 中间的 i 条边的边权之和为 m,改成分盒子问题,即 i 个相同小球分到 m 个不同的盒子中 —— $C_{m-1}^{i-1}$;
  • 剩下的 n-1-i 条边,对 A,B 之间的边权之和无影响,于是可以选择 1~m 的任何值 —— $m^{n-i-1}$;
  • 然后……剩下的还要考虑 除了 A,B 以及 A,B 之间的 (i+1) 个点 的 其他点的连接情况。

Part2/2. prufer序列

=重点=
任何一棵树都有一个 prufer 序列与之一一对应。
根据树能够得到唯一 prufer 序列;根据 prufer 序列可以得到唯一树。

于是我们可以生成一个序列,相当于生成了树。因为点的编号实际上没有影响,所以我们可以给 A,B 以及 A,B 之间的点一个新的编号,令这 (i+1) 个点的新编号为最大的 (i+1) 个点,那么剩下的点的 prufer 序列,除了最后一个被删除的点在 prufer 序列中的值只能为 A,B 及其之间的所有点,剩下的点在 prufer 序列中的值可以是 1~n 的任何一个点 —— $(i+1)n^{n-i-1}$。

于是我们发现了一个问题:当 i=n-1 时,$n^{n-i-1}=n^{-1}$,而且这个值是有意义的……所以要特殊处理为 n 的逆元。


Part3. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Lucky_Glass*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6;
const ll MOD=1e9+7;

int n,m,A,B;
ll Vans;
ll Efac[N+3],Einv[N+3];

ll ADD(ll A,ll B){return (A+B)%MOD;}
ll MNU(ll A,ll B){return (A-B+MOD)%MOD;}
ll TIM(ll A,ll B){return A*B%MOD;}
ll fC(int A,int B){return Efac[B]*Einv[A]%MOD*Einv[B-A]%MOD;}
ll fA(int A,int B){return Efac[B]*Einv[B-A]%MOD;}
ll QPow(ll A,ll B){if(B==-1) return QPow(A,MOD-2);ll Rr=1;while(B>0){if(B&1)Rr=TIM(Rr,A);A=TIM(A,A);B>>=1;}return Rr;}
void Process(){
Efac[0]=1;for(int i=1;i<=N;i++) Efac[i]=TIM(Efac[i-1],i);
Einv[N]=QPow(Efac[N],MOD-2);for(int i=N-1;i>=0;i--) Einv[i]=TIM(Einv[i+1],i+1);
}
int main(){
Process();
scanf("%d%d%*d%*d",&n,&m);
for(int Vbet=1;Vbet<n && Vbet<=m;Vbet++){ //the number of edges between A and B
ll Vct=1;
Vct=TIM(Vct,TIM(fA(Vbet-1,n-2),fC(Vbet-1,m-1)));
Vct=TIM(Vct,TIM(Vbet+1,QPow(n,n-Vbet-2)));
Vct=TIM(Vct,QPow(m,n-1-Vbet));
Vans=ADD(Vans,Vct);
}
printf("%lld\n",Vans);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!

0%