题解 ARC171B【Chmax】

考察题面中的操作究竟做了什么，不难发现其实是将所有满足 \(P_i > i\) 的 \(i\to P_i\) 连边，得到若干条链，然后 \(B_i\) 即为 \(i\) 所在链的最后一个节点。

显然，存在 \(A_i < i\) 时无解，存在 \(A_i\ne i\) 但 \(A_j = i\) 时也无解。

否则，每个 \(A_i\ne i\) 的位置填的数都唯一确定了（必须是下一个满足 \(A_j=A_i\) 的 \(j\)），只需计算将剩下的数填入 \(P\) 中，且满足 \(P_i < i\) 的方案数。这个是十分容易的。

// Problem: B - Chmax
// Contest: AtCoder - AtCoder Regular Contest 171
// URL: https://atcoder.jp/contests/arc171/tasks/arc171_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 2e5 + 5;

typedef Modint<998244353> mint;

int n, a[N], lst[N], vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    per(i, n, 1) {
    	if(a[i] < i) {
    		cout << 0 << endl;
    		return 0;
    	}
    	if(lst[a[i]]) vis[lst[a[i]]] = 1;
    	else if(i != a[i]) {
    		cout << 0 << endl;
    		return 0;
    	}
    	lst[a[i]] = i;
    }
    mint cnt = 0, ans = 1;
    rep(i, 1, n) {
	    cnt += !vis[i];
    	if(i == a[i]) {
	    	ans *= cnt;
	    	--cnt;
	    }
    }
    cout << ans << endl;
    return 0;
}