[ZJOI2017]仙人掌

日常在写博客之前的吐槽。

表示今天对着司公子的题解码完了此题(%%%司公子太巨辣),然后写完之后发现自己还是什么都不会。

然后lbc看了一天题解并且花了半小时妙了此题。

然后他随口就和我嘴了一下(所以这篇全文都是在转述lbc的理解和做法)

q234rty 太强辣

原题

有一个非常优美的性质:这是一个无重边的仙人掌。

然后我们就可以把问题转化一下,变成构造一个允许有重边每一条边必定包含在一个环里的仙人掌的方案数。

思考一下发现它们是等价的:你可以在原仙人掌的不在环内的边上加上重边,就构成了后一种仙人掌。

映射方案唯一确定(闭上眼睛感受一下嘛

再转化一下就变成了对于所有不在环上的边的路径覆盖方案数。

要注意判一下原图是不是仙人掌(不是就gg了啊

显而易见的,原图上有一堆非常不优雅的环,我们需要把它们去掉,然后就变成一个森林的问题了。

对所有树单独求和之后累乘起来嘛。

我们再来思考一下对于一棵树的做法。

对于任何一颗子树,由于有一条由父亲连向它的树边,必定会产生一条路径,一端在子树内一端在子树外。

当我们决定了路径的在子树内的一端未知在子树外的一端的时候,我们称其为待匹配路径。(原谅我的语文水平

显而易见的是一棵子树对父节点的影响有且仅有一条待匹配路径和一个方案数f[i]。

我们需要去掉一些带匹配路径将它们两两组合或者连向当前的根节点。

显然所有子树贡献的待匹配路径以外除了编号不同以外其他的性质都是相同的(废话

所以我们就可以定义一个函数g[i]=g[i-1]+(i-1)*(g[i-2])

感受一下就是,加入第i条路径,可以选择和根匹配也可以和前i-1条匹配。

最后不要忘记我们还要向上贡献一个待匹配路径。

怎么选呢。我们可以选根作为起点,或者继承任何一条路径

答案就是g[son]+g[son-1]*son,也就是g[son+1]辣!

然后就会发现对于任何一个点它的贡献都是g[out](出度

看不懂我的题解的话(或者说太长不看)只能说明我太菜了所以可以去看q234rty的题解(lbc太强辣!

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
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define lsg 998244353
inline ll read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(ll x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
int fh[1000010],flag[1000010],last[1000010],a[1000010][3],ff,ans,g[1000010],kk,t,n,m,x,y,dfn[1000010],kkk;
void check(int x,int fa){//判断是否是仙人掌并且标记环
fh[x]=fa;flag[x]=1;dfn[x]=++kkk;
for (int i=last[x];i;i=a[i][0])if (a[i][1]!=a[fa][1]){
if (flag[a[i][1]]){
if (dfn[a[i][1]]>dfn[x])continue;
int xx=x;while (xx!=a[i][1]){
if (a[fh[xx]][2]){ff=1;break;}
a[fh[xx]][2]=a[fh[xx]^1][2]=1;xx=a[fh[xx]][1];
}a[i][2]=a[i^1][2]=1;
}else check(a[i][1],i^1);
}
}void dfs(int x){
flag[x]=1;int dd=0;
for (int i=last[x];i;i=a[i][0])
if (!a[i][2]){
dd++;if (!flag[a[i][1]])dfs(a[i][1]);
}(ans*=g[dd])%=lsg;
}void doit(int x,int y){a[++kk][0]=last[x];a[kk][1]=y;a[kk][2]=0;last[x]=kk;}
signed main(){
g[0]=g[1]=1;g[2]=2;for (int i=3;i<=1000000;i++)g[i]=(g[i-1]+g[i-2]*(i-1))%lsg;
t=read();while (t--){
for (int i=1;i<=n;i++)last[i]=flag[i]=0;
n=read();m=read();ff=kkk=0;kk=1;
for (int i=1;i<=m;i++)x=read(),y=read(),doit(x,y),doit(y,x);
check(1,0);if (ff){puts("0");continue;}
for (int i=1;i<=n;i++)flag[i]=0;ans=1;
for (int i=1;i<=n;i++)if (!flag[i])dfs(i);
writeln(ans);
}
}
分享到