「UER#2」信息的交换

吉利题..

不难发现，置换中的每一个循环是独立的，每一个循环分别对应一个独立的联通块。

根据题目的性质，每一个联通块做的事情等价于其按照编号从小到大遍历的的dfs生成树做的事情，那么只需要考虑一棵dfs生成树做的事情即可。

对于一棵dfs生成树，将每个点的儿子按照编号从小到大排序，考虑节点 \(u\) 以及它的儿子 \(v_1,v_2..v_k\) ，其中 \(v_k\) 的权值最终会到 \(u\) 的位置上，\(\forall i<k,v_i\) 的值会先到 \(v_{i+1}\) 的位置上去，到访问到 \(v_i+1\) 的时候在继续做同样的事情，最终会到达 \(v_{i+1}\) 这棵子树最左边的叶子上。定义逆dfs序为先遍历编号大的儿子的dfs序，这个过程做完相当于节点 \(v\) 到了逆dfs序的前一位对应的节点上，根节点到逆dfs序上最后一位对应的节点。相当于按照逆dfs序做了一个置换！

那么只需要将每个循环对应的逆dfs序求出来，再计算有多少棵树的逆dfs序符合。对于一棵符合的树，其连上一些返祖边可以得到符合的图，大力DP一下即可，复杂度 \(\mathcal O(n^3)\) 。

code

/*program by mangoyang*/

#include <bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int ch = 0, f = 0; x = 0;

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

const int N = 505, mod = 998244353;

int vis[N], pw[N], a[N], f[N][N], h[N][N], c[N][N], n;

inline void up(int &x, int y){ x = x + y >= mod ? x + y - mod : x + y; }

inline int gao(vector<int> &A){

	if(!(int) A.size()) return 1;

	int m = A.size();

	for(int i = 0; i < m; i++)

		for(int j = i + 1; j < m; j++)

			c[i][j] = c[i][j-1] + (A[j] > A[i]);

	for(int i = 0; i < m; i++)

		for(int j = 0; j < m; j++) f[i][j] = 0;

	for(int i = 0; i < m; i++) f[i][i] = h[i][i] = 1;

	for(int i = m - 1; ~i; i--)

		for(int j = i + 1; j < m; j++){

			f[i][j] = h[i][j] = 1ll * f[i+1][j] * pw[c[i][j]] % mod;

			for(int k = i; k < j; k++) if(A[i] > A[k+1])

				up(f[i][j], 1ll * h[i][k] * f[k+1][j] % mod);

		}

	return f[0][m-1];

}

int main(){

	read(n), pw[0] = 1;

	for(int i = 1; i <= n; i++) read(a[i]);

	for(int i = 1; i <= n; i++) pw[i] = 2ll * pw[i-1] % mod;

	int ans = 1;

	for(int i = 1; i <= n; i++) if(!vis[i]){

		vector<int> A;

		vis[i] = 1;

		for(int p = a[i]; p != i; p = a[p])

			A.push_back(p), vis[p] = 1;

		ans = 1ll * ans * gao(A) % mod;

	}

	cout << ans << endl;

}

巴特西

「UER#2」信息的交换

「UER#2」信息的交换

code

最新文章

热门文章