WC2019 全国模拟赛第二场 T1 题解

又只会写T1…

题目链接

题意简述

给你一个排列 $p_{1..n}$,$a_{1..n}$ 为任意的一个排列,定义 $b[a_i]=a[p_i]$,求总共有多少个不同的 $b_{1..n}$ 。

做法

首先,对 $(i,p_i)$ 连边,会得到若干个环。

环上旋转一下($\forall i\text{ on the cycle : }i\rightarrow p_i$)得到的置换是本质相同的。节点个数相同的环互换一下是本质相同的。

先计算把 $n​$ 个节点分成若干个环的方案数:(用 $siz[i]​$ 表示第 $i​$ 个环的大小,$k​$ 表示环的个数,$sum[i]​$ 表示 $\sum\limits_{j=i}^ksiz[j]​$)

$$S_1=\prod\limits_{i=1}^kC_{sum[i]}^{siz[i]}$$

然后去掉节点个数相同的环互相交换:(用 $num[i]$ 表示节点个数为 $i$ 的环的个数)

$$S_2=\frac{S_1}{\prod\limits_{i=1}^nnum[i]!}$$

然后乘上每个环旋转(旋转造成的不同方案数即固定某个数后剩下的数的排列个数):

$$S_3=S_2\times\prod\limits_{i=1}^k(siz[i]-1)!$$

$S_3$ 就是最终的答案了。

参考代码

noi.ac 上最短解(其实计算方式和我是一样的..):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
#define mn 1111111
using namespace std;
long long n,i=1,s=1,j,x,p=998244353,a[mn],f[mn],v[mn],t[mn];
int main()
{
scanf("%lld",&n); f[0]=f[1]=1; for (;i<=n;i++) scanf("%lld",a+i);
for (i=2;i<=n;i++) f[i]=f[p%i]*(p-p/i)%p,(s*=i)%=p;
for (i=1;i<=n;i++)
if (!v[i])
{
for (j=i,x=0;!v[j];x++,j=a[j]) v[j]=1;
(s*=f[x]*f[++t[x]]%p)%=p;
}
printf("%lld",s);
}

我自己赛时的辣鸡写法:

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
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

int read()
{
int out=0;
char c;
while (!isdigit(c=getchar()));
for (;isdigit(c);c=getchar())
{
out=out*10+c-'0';
}
return out;
}

const int N=1000010;
const int M=998244353;

void dfs(int u);
int c(int a,int b);

int n,p[N],dfn[N],low[N],sta[N],dfncnt,top,siz[N],tot,num[N];
int x,y,jc[N],inv[N],ans=1,sum;
bool ins[N];

int main()
{
int i;

n=sum=read();

for (i=1;i<=n;++i)
{
p[i]=read();
}

for (i=1;i<=n;++i)
{
if (dfn[i]==0)
{
dfs(i);
}
}

jc[0]=jc[1]=inv[0]=inv[1]=1;
for (i=2;i<=n;++i)
{
inv[i]=(1ll*M*M-1ll*(M/i)*inv[M%i])%M;
}
for (i=2;i<=n;++i)
{
jc[i]=(1ll*jc[i-1]*i)%M;
inv[i]=(1ll*inv[i-1]*inv[i])%M;
}

for (i=1;i<=tot;++i)
{
ans=1ll*ans*c(sum,siz[i])%M;
sum-=siz[i];
}

for (i=1;i<=n;++i)
{
ans=1ll*ans*inv[num[i]]%M;
}

for (i=1;i<=tot;++i)
{
ans=1ll*ans*jc[siz[i]-1]%M;
}

cout<<ans;

return 0;
}

int c(int a,int b)
{
if (a==b||b==0)
{
return 1;
}
return 1ll*(1ll*jc[a]*inv[b]%M)*inv[a-b]%M;
}

void dfs(int u)
{
dfn[u]=low[u]=++dfncnt;
sta[++top]=u;
ins[u]=true;
if (dfn[p[u]]==0)
{
dfs(p[u]);
low[u]=min(low[u],low[p[u]]);
}
else if (ins[p[u]])
{
low[u]=min(low[u],dfn[p[u]]);
}
if (low[u]==dfn[u])
{
siz[++tot]=1;
while (sta[top]!=u)
{
++siz[tot];
ins[sta[top--]]=false;
}
ins[sta[top--]]=false;
++num[siz[tot]];
}
}

所以说不要看到环就 tarjan…