OI - Sasha and Interesting Fact from Graph Theory(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

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

发表于 更新于 分类于 Valine：

事实是我还是不会做……

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，欢迎提问！