自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:28:29，当前版本为作者最后更新于2021-06-16 18:42:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单的线性做法。

从新图的起点走到 $(a_1,a_2...a_k)$，相当于在 $k$ 张图上同时从 $1$ 走到 $a_i$。

如果某张图比其他图先走到，那么这个点可以任选一条经过它的边反复横跳。

所以只需要保证每张图上从 $1$ 走到 $a_i$ 距离的奇偶性相同。

首先通过 bfs，预处理每张图上 $1$ 到所有点的长度为奇数和偶数的最短路。

记 $ji_i$ 为奇数最短路，$ou_i$ 为偶数最短路，若不存在则为 $\inf$。

则新图的起点到 $(a_1,a_2...a_k)$ 的距离，等于 $\min(\max(ji_{a_i}),\max(ou_{a_i}))$。

这个式子不好处理，通过 $a+b=\min(a,b)+\max(a,b)$，转化为 $\max(ji_{a_i})+\max(ou_{a_i})-\max(\max(ji_{a_i},ou_{a_i}))$。

将三部分分别计算，每次分别记 $w_i=ji_i,ou_i,\max(ji_i,ou_i)$。

考虑对于每个点 $j$，求出 $j\in a_i$，且 $w_j=\max(w_{a_i})$ 的方案数。

发现这样会算重，考虑对于相同的 $w_j$，按所属图的编号为第二关键字比较。

于是只需要将所有点按 $w_j$ 为第一关键字，图的编号为第二关键字排序，因为值域是点数级别，所以这部分复杂度是线性。

然后按顺序依次加入每个点，加入属于图 $k$ 的点 $j$ 时的方案数，就是除 $k$ 以外所有图已经被加入的点的个数的乘积。

预处理乘法逆元可以 $O(1)$ 加点。

总复杂度线性。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3,P=1e9+7;
basic_string<int>v[3][N+1];
int iv[N],a[N],o,u;
void in(){
	int n,m,i,j;
	basic_string<int>ji,ou;
	vector<basic_string<int>>g;
	queue<int>q;
	scanf("%d%d",&n,&m),ji.assign(n+1,N),ou.assign(n+1,N),g.resize(n+1);
	while(m--)scanf("%d%d",&i,&j),g[i]+=j,g[j]+=i;
	q.push(1),ou[1]=0;
	while(q.size()){//bfs
		i=q.front(),q.pop();
		if(i>n){
			i-=n;
			for(int j:g[i])if(ou[j]==N)ou[j]=ji[i]+1,q.push(j);
		}else for(int j:g[i])if(ji[j]==N)ji[j]=ou[i]+1,q.push(j+n);
	}
	for(i=1;i<=n;++i)v[0][ji[i]]+=u,v[1][ou[i]]+=u,v[2][max(ji[i],ou[i])]+=u;
}
int get(basic_string<int>*v){
	int i,s=0,t=1,c=0;
	for(i=0,memset(a,0,N*4);i<N;++i)for(int j:v[i]){//加点
		if(a[j])t=t*1ll*iv[a[j]]%P;else ++c;
		if(c==o)s=(s+t*1ll*i)%P;
		t=t*1ll*(++a[j])%P;
	}
	return s;
}
int main(){
	for(iv[1]=1,u=2;u<N;++u)iv[u]=(P-P/u)*1ll*iv[P%u]%P;//预处理逆元
	for(scanf("%d",&o),u=1;u<=o;++u)in();
	printf("%d",((get(v[0])+get(v[1])-get(v[2]))%P+P)%P);
	return 0;
}