[置换 + DP] UOJ114. [UER #2] 信息的交换

吉老师的好题。要看懂题目的操作是在干什么,然后就可做了。

自己画画图可以发现,对于原图每个连通块,是按小标号优先 \(dfs\) 出了一颗树,

注意到一个重要的结论:每个联通块最后的结果看作一个置换,这个置换一定是个完整的循环。

正确性比较显然,就是不容易直接想到。

知道这个就好了,每个循环对应原图的一个连通块,每个循环是独立的,分别搞:

循环的那个序列可以看作是按大标号优先的 \(dfs\) 序。可以 \(DP\) 求有多少符合 \(dfs\) 的图。

\(g(i,j)\) 表示区间 \([i,j]\) 的方案数。 \(f(i,j)\) 表示区间构成一些儿子子树的方案数。

转移比较容易,具体看代码。

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=505,P=998244353;
int n,ans=1,a[maxn],b[maxn],f[maxn][maxn],g[maxn][maxn],h[maxn][maxn];
bool vis[maxn];
int DP(){
for(int i=1;i<=b[0];i++) f[i][i]=g[i][i]=1;
for(int i=1;i<=b[0];i++){
h[i][i]=1;
for(int j=i+1;j<=b[0];j++) h[i][j]=h[i][j-1]*(b[i]<b[j]?2:1)%P;
}
for(int i=b[0];i>=1;i--)
for(int j=i+1;j<=b[0];j++){
f[i][j]=g[i+1][j]; g[i][j]=(LL)f[i][j]*h[i][j]%P;
for(int k=i;k<=j-1;k++)
if(b[k+1]<b[i]) g[i][j]=(g[i][j]+(LL)f[i][k]*h[i][k]%P*g[k+1][j])%P;
}
return f[1][b[0]];
}
int main(){
freopen("uoj114.in","r",stdin);
freopen("uoj114.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
if(!vis[i]){
b[0]=0;
for(int x=i;!vis[x];x=a[x]) vis[x]=true, b[++b[0]]=x;
ans=(LL)ans*DP()%P;
}
printf("%d\n",ans);
return 0;
}