专栏文章

P11563 Sol

CCarroT1212菜萝卜
P11563题解参与者 5已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@miqjdv35
此快照首次捕获于
2025/12/04 05:46
3 个月前
此快照最后确认于
2025/12/04 05:46
3 个月前
查看原文
我擦，企鹅罐！生存战略！
挺好的性质题。写详细亿点。
排列可以看成有向环集合来计数。设在 pp 上对于每个 ii，在图上连接 i↔pii\leftrightarrow p_i 得到的无向图为 G1G_1，在 aa 上对于每个 ii 连接 i→aii\to a_i 得到的有向图为 G2G_2。那么 aa 合法仅当 G1G_1 的每条边的其中一个方向都在 G2G_2 中出现。G1G_1 已知了，我们需要知道合法的 G2G_2 数，考虑刻画。
首先由于 aa 是排列，G2G_2 只包含有向环，那么 G1G_1 出现一个度数 ≥3\ge 3 的点就包没合法 G2G_2 的。考虑到 G1G_1 出来会是个基环森林，都不能有森林了，看起来 G1G_1 也必须是一堆环构成的啊？
（观察样例）发现有个奇怪情况：G1G_1 里有二元环。你会发现这里我们应该要将这个二元环当作一条无向边来看待，因为 G2G_2 只需要有一条有向边就可以同时消灭二元环里的两条边。
于是把二元环换成无向边后 G1G_1 里出现了链！现在看看怎么个事。
  • G1G_1 中有点度数 ≥3\ge 3，无解。
  • 对于 G1G_1 中的自环，不用管它，它在 G2G_2 里还是自环。
  • G1G_1 中点数 ≥3\ge 3 的环，在 G2G_2 中这些边都需要出现，每个环都有两种定向方法，统计环数 kk 最后乘上 2k2^k。
  • G1G_1 中的链，我们在 G2G_2 中需要给每条链定向，然后用若干条有向边把它们的两端连接起来，变成若干有向环集合。设链数为 xx，要是把定向完的链看成一个大点，那这个连接过程其实就是根据一个长度为 xx 的排列建 G2G_2 的过程，连接方案数为 x!x!（每条链定向完后只有一个点能接受入边，一个点输出出边，而外部新连的边的方向已经根据连接情况确定）。而每条链内部有两种定向方式，再乘上 2x2^x……
别急，还有高手！如果 G2G_2 里又连出了二元环，这时这个环的两种定向方式在 G2G_2 里看起来是一样的！算重到起飞！
这种情况要求 G1G_1 里存在一个孤单的二元环被变成了一条无向边，然后我们在后期连接的时候直接将它的两端连了起来。设 G1G_1 中这样单独的一条无向边作一条链的条数为 yy。
没事还可以容斥，我们钦定其中 ii 条边在 G2G_2 里被当成二元环的另一个方向算重的方案数为 fif_i。有 fi=(yi)2x−i(x−i)!f_i=\binom{y}{i}2^{x-i}(x-i)!。最后 ans=2k∑i=0y(−1)ifians=2^k\sum\limits_{i=0}^y(-1)^if_i。
实现就是看看 G1G_1 里上面几种东西都有几种，算就完了。小心漏了什么阴间情况。
CPP
const ll J=1e18,N=1e6+7,P=998244353;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll fac[N],fnv[N];
struct init { init() {
	fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
	fnv[N-1]=qp(fac[N-1]); for (ll i=N-1;i;i--) fnv[i-1]=fnv[i]*i%P;
} } A;
ll C(ll x,ll y) { return x<0||y<0||x<y?0:fac[x]*fnv[y]%P*fnv[x-y]%P; }
ll n,a[N],ans,vis[N];
ll c3,c21,c22;
vector<ll> e[N];
void no() { cout<<"0",exit(0); }
void get(ll p) {
	if (e[p].size()>1) no();
	vis[p]=1;
	if (e[p].size()==1&&!vis[e[p][0]]) get(e[p][0]);
}
void mian() {
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),e[a[i]].pb(i);
	for (ll i=1;i<=n;i++) if (!vis[i]) {
		if (a[i]==i) {
			if (e[i].size()>1) no();
			vis[i]=1;
		}
		else if (a[a[i]]==i) {
			ll x=i,y=a[i],flg=0;
			vis[x]=vis[y]=1;
			if (e[x].size()>2||e[y].size()>2) no();
			if (e[x].size()==2) flg=1,get(e[x][0]^e[x][1]^y);
			if (e[y].size()==2) flg=1,get(e[y][0]^e[y][1]^x);
			flg?c22++:c21++;
		}
	}
	for (ll i=1;i<=n;i++) if (!vis[i]) {
		if (!e[i].size()) no();
		c3++,get(i);
	}
	ll ans=0;
	for (ll i=0;i<=c21;i++) (ans+=(i&1?P-1:1)*C(c21,i)%P*qp(2,c21+c22-i)%P*fac[c21+c22-i])%=P;
	cout<<ans*qp(2,c3)%P;
}

评论

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

正在加载评论...