专栏文章

题解：AT_agc070_b [AGC070B] Odd Namori

ttobie
AT_agc070_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqkxbxm
此快照首次捕获于
2025/12/04 06:29
3 个月前
此快照最后确认于
2025/12/04 06:29
3 个月前
查看原文
我嘞个容斥仙人啊！
首先这个 2cnt2^{\mathrm{cnt}} 就很奇妙，考虑赋予其一个组合意义：每个环要么选上，要么不选。注意到这里可以顺便容斥掉出现偶环的情况。具体地，选出一个偶环乘上 −1-1，选出一个奇环乘上 11，则存在奇环的图都会被我们容斥掉。
假设我们选出的环上的点的集合为 SS，显然 1∈S1\in S，则剩下的点不能和父亲连边，有一个 (n−1)n−∣S∣(n-1)^{n-|S|} 的贡献，对于 1∉S1\notin S 可能需要特殊处理。
交换求和顺序，我们先钦定 SS，考虑 SS 内部的贡献 f(S)f(S)。

Lamma 1：如果不考虑树边，则 f(S)=[∣S∣=1]f(S)=[|S|=1]。

证明：
考虑构造双射：交换编号最小节点和编号最大节点的出边。
此时会有两个环合并成一个大的环，或者一个大环被拆成两个小环，偶环个数奇偶性必然改变。
所以若 ∣S∣>1|S|>1，则 2f(S)=02f(S)=0，进而 f(S)=0f(S)=0。
现在我们把没有考虑到的条件加回来。首先钦定的树边肯定是若干条链，把链缩起来后可以得到偶链和奇链，可以缩点成为奇点和偶点。稍加推理可以得到第二个重要性质。

Lamma 2：考虑树边的情况下，f(S)=1f(S)=1 当且仅当 SS 是一个祖先后代链。

证明：
如果缩点后存在至少两个点，则 f(S)=0f(S)=0，所以现在只有一个点，并且和 SS 有关的所有树边都需要被钦定。
如果这个点是偶点，则有奇数条被钦定的边；如果这个点是奇点，则有偶数条被钦定的边，所以总共有偶数个 −1-1 相乘，贡献为 −1-1。
所以我们只需要统计出长度为 dd 的链有多少条，带入公式计算即可，时间复杂度线性。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9,mod=998244353;
int n,dep[N],tj[N];
int pw[N],ans;
signed main()
{
	scanf("%d",&n);
	for(int i=2,x;i<=n;i++) scanf("%d",&x),dep[i]=dep[x]+1;
	for(int i=1;i<=n;i++) tj[dep[i]]++;
	for(int i=n;i>=1;i--) (tj[i]+=tj[i+1])%=mod;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*(n-1)%mod;
	ans=1ll*pw[n-1]*n%mod;
	for(int i=1;i<=n;i++) (ans+=pw[n-dep[i]-1])%=mod;
	for(int i=1;i<n;i++) (ans+=1ll*pw[n-i-1]*tj[i]%mod*n%mod)%=mod;
	(ans+=tj[n])%=mod;
	printf("%d\n",ans);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...