排列与置换换+容斥+多项式生成函数启发式合并：[Gym-103446B]

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134243178

https://vjudge.net/contest/591700#problem/G

看到排列，先考虑置换换，题意转化为置换环相邻的不能再最终序列上相邻

而这个过程看起来很容斥，所以我们容斥：至少要 xx 个相邻

我们发现每个置换环的所有边不能全部同时被选，所以我们每个置换环要分开考虑，最后再乘起来

然而这样的复杂度会炸。但是我们可以写成生成函数的形式，然后用启发式合并起来

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//srand(time(0));
#define N 2000010
//#define M
#define mo 998244353
#define G 3
inline int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}
int fac[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i=fac[0]=1; i<=n; ++i) fac[i]=fac[i-1]*i%mo; 
	ifac[n]=pw(fac[n], mo-2); 
	for(i=n-1; i>=0; --i) ifac[i]=ifac[i+1]*(i+1)%mo; 
}
int C(int n, int m) {
	if(m>n) return 0;
	return fac[n]*ifac[m]%mo*ifac[n-m]%mo; 
}
const int Gi=pw(G, mo-2); 
int Mod(int a) { if(a>=mo || a<=-mo) a%=mo; if(a<0) a+=mo; return a; }
void Add(int &a, int b) { a+=b; Mod(a); }
void Mul(int &a, int b) { Mod(b); a*=b; Mod(a); } 
int rev[1<<22]; 
inline void revese(int n, int l) {
	for(int i=0; i<n; ++i) rev[i]=((rev[i>>1]>>1)|((i&1)<<l-1)); 
}
inline void NTT(int *P, int n, int op) {
	int i, j, k, w, W, X, Y; 
	for(i=0; i<n; ++i) if(i<rev[i]) swap(P[i], P[rev[i]]); 
	for(i=1; i<n; i<<=1) {
		W=pw(op==1 ? G : Gi, (mo-1)/(i<<1)); //*****
		for(j=0; j<n; j+=(i<<1)) {
			for(k=0, w=1; k<i; ++k, w=Mod(w*W)) {
				X=P[j+k], Y=Mod(w*P[j+k+i]); 
				P[j+k]=Mod(X+Y), P[j+k+i]=Mod(X-Y); 
			}
		}
	}
	if(op==1) return ; 
	int inv=pw(n, mo-2); 
	for(i=0; i<n; ++i) P[i]=P[i]*inv%mo; 
}
struct node {
	int x, len; 
	bool operator <(const node &A) const {
		return len>A.len; 
	}
};
priority_queue<node>q; 
int u, ve; 
int n, m, i, j, k, T;
int f[N], g[N], rt; 
int a[N]; 
int F[N], w[N], ans; 
vector<int>v[N]; 

int fa(int x) {
	if(F[x]==x) return x; 
	return F[x]=fa(F[x]); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	srand(time(0)); 
	m=read();  init(m); 
	for(i=1; i<=m; ++i) F[i]=i; 
	for(i=1; i<=m; ++i) k=read(), F[fa(i)]=fa(k); 
	for(i=1; i<=m; ++i) w[fa(i)]++; 
	for(i=1; i<=m; ++i) if(fa(i)==i) {
		debug("%lld %lld\n", i, w[i]); 
		++n; 
		for(j=0; j<w[i]; ++j) v[n].pb(C(w[i], j)); v[n].pb(0); 
		q.push({n, w[i]+1}); 
	}
	while(!q.empty()) {
		u=q.top().x; q.pop(); 
		if(q.empty()) break; 
		ve=q.top().x; q.pop(); 
		k=++n; 
		int len1=v[u].size()-1, len2=v[ve].size()-1; 
		int len=len1+len2+1, m=len, n, le; //new n!
		for(n=1, le=0; n<=m; n<<=1) ++le; 
		revese(n, le);  
		for(i=0; i<v[u].size() && i<n; ++i) f[i]=v[u][i]; for(; i<n; ++i) f[i]=0; 
		for(i=0; i<v[ve].size() && i<n; ++i) g[i]=v[ve][i]; for(; i<n; ++i) g[i]=0; 
		for(i=0; i<n; ++i) debug("%lld ", f[i]); debug("\n"); 
		for(i=0; i<n; ++i) debug("%lld ", g[i]); debug("\n"); 
		NTT(f, n, 1); NTT(g, n, 1); 
		for(i=0; i<n; ++i) f[i]=Mod(f[i]*g[i]); 
		NTT(f, n, -1); 
		for(i=0; i<n; ++i) v[k].pb(f[i]); 
		q.push({k, n}); 
	}
	debug("%lld\n", n); 
	for(i=0; i<m; ++i) debug("%lld ", v[n][i]); debug("\n"); 
	for(i=0, k=1; i<m; ++i, k=-k) Add(ans, v[n][i]*k%mo*fac[m-i]%mo); 
	ans=Mod(ans); 
	printf("%lld\n", ans); 
	return 0;
}