「51nod 1907」小C的游戏

发表于

小 C 在无向图上玩这样一个游戏。

小 C 可以任选一点作为起点。每次他可以进行两种操作：

  • 移动到一个相邻的结点。
  • 使用一次魔法，移动到图中任意一个结点。

当他访问图中每个结点至少 11 次时，游戏结束。注意他必须使用不超过 n−1n-1 次魔法。

游戏结束时，如果他使用了 kk 次魔法，则他本轮游戏的花费为 aka_k 。

现有一个 nn 个点 mm 条边的无向连通图 GG 。图 GG 中任意一条边至多属于一个环。

小 C 希望知道，在图 GG 的所有生成子图进行上述游戏所需花费的最小值之和。

由于答案可能很大，将答案对 998244353998244353 取模。

Constraints

1≤n≤300001 \leq n \leq 30000 ， n−1≤m≤2n−2n-1 \leq m \leq 2n-2 ， 0≤ai≤1090 \leq a_i \leq 10^9

可能有重边，但不会有自环。

图 G′(V′,E′)G'(V',E') 是图 G(V,E)G(V,E) 的生成子图当且仅当 V′=V,E′⊆EV' = V , E' \subseteq E 。

简单环定义为一个顶点序列 v1,v2,⋯,vm(m≥2)v_1, v_2, \cdots , v_m (m \ge 2) ，其中 viv_i 与 vi+1v_{i+1} 相邻， v1v_1 与 vmv_m 相邻，且 viv_i 互不相同。

Solution

首先可以确定，在一个连通块内部移动不需要魔法，即只有跨越连通块使用的魔法是必要的，即最少魔法使用次数为连通块个数 −1-1 。问题转换为，求出连通块个数为 ii 的生成子图的方案数。

据题意，给出的图是仙人掌图，可以被分解为若干树边和环。我们将环和树边分开考虑，并构造出对应的生成函数，xix^i 表示当前部分贡献 ii 个连通块的方案数，最后将得到的所有多项式相乘即可。

1.1. 对于一条树边，删去即贡献 11 个连通块，保留则无贡献，即 f(x)=x+1f(x)=x+1 。

2.2. 对于一个包含n条边的环，在删去第一条边时无贡献，从第二条边开始每删去一条边对连通块数量贡献 +1+1 ，即 f(x)=∑i=0n−1(ni+1)xi+1f(x)=\sum_{i=0}^{n-1}\binom{n}{i+1}x^i+1 。

在多项式相乘时使用启发式合并，保证时间复杂度为 O(nlog2n)O(nlog^2n) 。

在最后统计答案时，由于 aa 序列不一定单调递增，一个连通块个数为 ii 的生成子图的实际最小代价为后缀最小值。且因为初始连通块个数为 11 ，最终 xix^i 的系数实际代表的是包含 i+1i+1 个连通块的生成子图的方案数。

Code

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int N=131072+5;
const int mod=998244353;
int n,m,x,y,cnt,tot,sum,*cur;
int nn,al,bl,*acur,*bcur;
int first[N],val[N],fac[N],fav[N],bel[N];
int hx[N],hy[N],fa[N],deep[N];
int length[N],o[10000005];
int a[N],b[N];
struct edge{int to,next;}e[N*2];
struct node
{
	int n,*cur;
	bool operator < (const node& a)const{return n>a.n;}
}aa,bb;
priority_queue<node> q;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int min(int a,int b){return a<b?a:b;}
int C(int n,int m){return 1ll*fac[n]*fav[m]%mod*fav[n-m]%mod;}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
int find(int t){return t==bel[t]?t:bel[t]=find(bel[t]);}
void dfs(int x,int last)
{
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==last)continue;
		deep[to]=deep[x]+1;
		fa[to]=x;dfs(to,x);
	}
}
int dis(int x,int y)
{
	int ans=1;
	while(x!=y)
	{
		if(deep[x]<deep[y])swap(x,y);
		x=fa[x];ans++;
	}
	return ans;
}
int power(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}
	return ans;
}
void ntt(int *a,int n,int f)
{
	int k=0;while((1<<k)<n)k++;
	for(int i=0;i<n;i++)
	{
		int t=0;
		for(int j=0;j<k;j++)
			if(i&(1<<j))t|=(1<<(k-j-1));
		if(i<t)swap(a[i],a[t]);
	}
	for(int l=2;l<=n;l<<=1)
	{
		int m=l>>1,nw=power(3,(mod-1)/l);
		if(f==-1)nw=power(nw,mod-2);
		for(int *p=a;p!=a+n;p+=l)
		{
			int w=1;
			for(int i=0;i<m;i++)
			{
				int t=1ll*p[m+i]*w%mod;
				p[m+i]=(p[i]-t+mod)%mod;
				p[i]=(p[i]+t)%mod;
				w=1ll*w*nw%mod;
			}
		}
	}
	if(f==-1)
	{
		int inv=power(n,mod-2);
		for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
	}
}
int main()
{
	n=read();m=read();
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	fav[n]=power(fac[n],mod-2);
	for(int i=n;i>=1;i--)fav[i-1]=1ll*fav[i]*i%mod;
	for(int i=1;i<=n;i++)bel[i]=i;
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=n-1;i>=1;i--)val[i]=min(val[i],val[i+1]);
	for(int i=1;i<=m;i++)
	{
		x=read();y=read();
		if(find(x)!=find(y))bel[find(x)]=find(y),ins(x,y),ins(y,x);
		else tot++,hx[tot]=x,hy[tot]=y;
	}
	dfs(1,-1);sum=n-1;cnt=0;
	for(int i=1;i<=tot;i++)
		length[i]=dis(hx[i],hy[i]),sum-=(length[i]-1);
	if(sum>=0)
	{
		cur=&o[cnt];cnt=sum+1;
		for(int i=0;i<=sum;i++)cur[i]=C(sum,i);
		q.push((node){sum,cur});
	}
	for(int i=1;i<=tot;i++)
	{
		cur=&o[cnt];cnt+=length[i];
		cur[0]=length[i]+1;
		for(int j=1;j<=length[i]-1;j++)cur[j]=C(length[i],j+1);
		q.push((node){length[i]-1,cur});
	}
	while(q.size()>1)
	{
		aa=q.top();q.pop();
		al=aa.n;acur=aa.cur;
		bb=q.top();q.pop();
		bl=bb.n;bcur=bb.cur;
		for(nn=1;nn<=al+bl;nn<<=1);
		for(int i=0;i<nn;i++)a[i]=b[i]=0;
		for(int i=0;i<=al;i++)a[i]=acur[i];
		for(int i=0;i<=bl;i++)b[i]=bcur[i];
		ntt(a,nn,1);ntt(b,nn,1);
		for(int i=0;i<nn;i++)a[i]=1ll*a[i]*b[i]%mod;
		ntt(a,nn,-1);
		cur=&o[cnt];cnt+=al+bl+1;
		for(int i=0;i<=al+bl;i++)cur[i]=a[i];
		q.push((node){al+bl,cur});
	}
	int ans=0;aa=q.top();cur=aa.cur;
	for(int i=1;i<=n;i++)ans=(ans+1ll*val[i]*cur[i-1])%mod;
	printf("%d",ans);
	return 0;
}