C++ 解法, 执行用时: 154ms, 内存消耗: 4136K, 提交时间: 2021-11-28 13:35:04

#include<bits/stdc++.h>
#define P 998244353
#define N 220000
using namespace std;
int a[N],p[N],fac[N],ifac[N];
int r[N],q[N],b[N],f[N];
int lim=1<<17;
int n;
int dfs(int x){
	if(q[x]==1)return 0;
	q[x]=1;
	return dfs(p[x])+1;
}
int power(int x,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1LL*ans*x%P;
		x=1LL*x*x%P;
		k>>=1;
	}
	return ans;
}
void DFT(int a[],int lim,int opt){
	int i,j,k,m,gn,g,tmp;
	for(int i=0;i<lim;i++)if(r[i]<i)swap(a[i],a[r[i]]);
	for(m=2;m<=lim;m<<=1){
		k=m>>1;
		gn=power(3,(P-1)/m);
		for(int i=0;i<lim;i+=m){
			g=1;
			for(j=0;j<k;++j,g=1LL*g*gn%P){
				tmp=1LL*a[i+j+k]*g%P;
				a[i+j+k]=(a[i+j]-tmp+P)%P;
				a[i+j]=(a[i+j]+tmp)%P;
			}
		}
	}
	if(opt==-1){
		reverse(a+1,a+lim);
		int inv=power(lim,P-2);
		for(i=0;i<lim;i++)a[i]=1LL*a[i]*inv%P;
	}
}
long long C(long long n,long long m){
	return 1LL*fac[n]*ifac[m]%P*ifac[n-m]%P;
}
void pre(){
	fac[0]=ifac[0]=1;
	for(int i=1;i<=lim;i++)fac[i]=1LL*fac[i-1]*i%P;
	ifac[lim]=power(fac[lim],P-2);
	for(int i=lim-1;i>=0;i--)ifac[i]=1LL*ifac[i+1]*(i+1)%P;
}
int main(){
	pre();
	for(int i=0;i<lim;i++)r[i]=(i&1)*(lim>>1)+(r[i>>1]>>1);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++){
		if(q[i]==0)f[dfs(i)]++;
	}
	a[0]=1;
	DFT(a,lim,1);
	for(int i=1;i<=n;i++){
		if(f[i]==0)continue;
		memset(b,0,sizeof(b));
		for(int j=0;j<i;j++){
			b[j]=C(i,j);
		}
		DFT(b,lim,1);
		for(int j=0;j<lim;j++)a[j]=1LL*a[j]*power(b[j],f[i])%P;
	}
	DFT(a,lim,-1);
	long long ans=0;
	long long flag=1;
	for(int i=0;i<lim;i++){
		ans+=1LL*fac[n-i]*a[i]%P*flag%P;
		flag=P-flag;
	}
	ans%=P;
	printf("%lld\n",ans);
}