Description

按照字典序升序给所有[1,n][1, n] 的排列标号,从 11 开始。 小 DD 曾经从中选择了一个排列 p1,p2,...,pn{p_1, p_2 ,..., p_n },但现在他忘记了这个排列的部分元素,于是 他决定用00 表示他忘记的元素 pip_i 他想知道所有可能被选中的排列的序号之和,对 998244353998244353 取模。

Constraints

n≤3×105n\le 3\times 10^5

Solution

假设有 xx 个未确定元素,那么有 x!x! 个可行排列 P 。我们令标号从 00 开始,只需给答案加上 x!x! 即可,即只需要计算有多少个排列排在它前面。

容易推出一个排列 aa 的序号:

∑i=1n(n−i)!(ai−1−∑j=1i−1[aj<ai])\sum_{i=1}^{n}{(n-i)!(a_i-1-\sum_{j=1}^{i-1}{[a_j<a_i]})}

那么答案为

∑a∈P∑i=1n(n−i)!(ai−1−∑j=1i−1[aj<ai])\sum_{a\in P}\sum_{i=1}^{n}{(n-i)!(a_i-1-\sum_{j=1}^{i-1}{[a_j<a_i]})}

=∑i=1n(n−i)!∑a∈P(ai−1−∑j=1i−1[aj<ai]) = \sum_{i=1}^{n}{(n-i)! \sum_{a\in P}(a_i-1-\sum_{j=1}^{i-1}{[a_j<a_i]})}

=∑i=1n(n−i)!(∑a∈P(ai−1)−∑j∈[1,i),pj=0∑a∈P[aj<ai]−∑j∈[1,i),pj≠0∑a∈P[aj<ai]) = \sum_{i=1}^{n}{(n-i)!( \sum_{a\in P}(a_i-1)-\sum_{j\in [1,i), p_j=0} \sum_{a\in P} {[a_j<a_i]}} - \sum_{j\in [1,i), p_j\neq0} \sum_{a\in P} {[a_j < a_i]})

另SS集合为未出现过的数字集合

当pi≠0p_i \neq 0

∑a∈P(ai−1)=(pi−1)∗x!\sum_{a\in P}(a_i - 1) = (p_i - 1) * x!

∑j∈[1,i),pj=0∑a∈P[aj<ai]=(∑j∈[1,i)[pj=0])∗(∑k∈S[k<pi])∗(x−1)!\sum_{j\in [1,i), p_j=0} \sum_{a\in P} {[a_j < a_i]} = (\sum_{j\in[1, i)}[p_j=0]) * (\sum_{k\in S}[k<p_i]) * (x - 1)!

∑j∈[1,i),pj≠0∑a∈P[aj<ai])=∑j∈[1,i),pj≠0[pj<pi]∗x!\sum_{j\in [1,i), p_j\neq0} \sum_{a\in P} {[a_j < a_i]}) = \sum_{j\in [1, i), p_j\neq 0}[p_j<p_i] * x!

当pi=0p_i=0

∑a∈P(ai−1)=∑k∈S(k−1)∗(x−1)!\sum_{a\in P}(a_i - 1) = \sum_{k\in S}(k - 1) * (x - 1)!

∑j∈[1,i),pj=0∑a∈P[aj<ai]=(∑j∈[1,i)[pj=0])∗x∗(x−1)2∗(x−2)!\sum_{j\in [1,i), p_j=0} \sum_{a\in P} {[a_j < a_i]} = (\sum_{j\in[1, i)}[p_j=0]) * \frac{x*(x-1)}{2} * (x-2)!

∑j∈[1,i),pj≠0∑a∈P[aj<ai])=∑j∈[1,i),pj≠0∑k∈S[k>pj]∗(x−1)!\sum_{j\in [1,i), p_j\neq0} \sum_{a\in P} {[a_j < a_i]}) = \sum_{j\in [1, i), p_j\neq 0}\sum_{k\in S}[k > p_j] * (x - 1)!

然后用预处理/树状数组优化即可做到O(nlogn)O(n\log n)

Code

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

#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 3e5 + 100, Mod = 998244353;

int N, A[Maxn];

namespace BIT
{
#define lowbit(x) (x & (-x))
	int sum[Maxn];
	inline void add (int x, int val) { while (x <= N) { sum[x] += val; x += lowbit(x); } }
	inline int query (int x) { int ans = 0; while (x) { ans += sum[x]; x -= lowbit(x); } return ans; }
}

inline void Add (int &x, int y) { x += y; x -= x >= Mod ? Mod : 0; }

int fac[Maxn], Sum[Maxn], Vis[Maxn];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("c.in", "r", stdin);
	freopen("c.out", "w", stdout);
#endif
	N = read();
	int cnt = 0, sum = 0;
	fac[0] = 1;
	for (int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % Mod;
	for (int i = 1; i <= N; ++i) A[i] = read(), cnt += !A[i], Vis[A[i]] = 1;
	for (int i = 1; i <= N; ++i) Sum[i] = Sum[i - 1] + !Vis[i], Add(sum, (!Vis[i] ? (i - 1) : 0));
	int ans = fac[cnt], tot1 = 0, tot2 = 0;
	for (int i = 1; i <= N; ++i)
	{
		int tmp = 0;
		if (A[i])
		{
			Add (tmp, 1ll * (A[i] - 1) * fac[cnt] % Mod);
			if (cnt) Add (tmp, Mod - (1ll * tot1 * Sum[A[i] - 1] % Mod * fac[cnt - 1] % Mod));
			Add (tmp, Mod - (1ll * BIT :: query (A[i] - 1) * fac[cnt] % Mod));
			Add (tot2, (cnt - Sum[A[i]])); BIT :: add (A[i], 1);
		}
		else
		{
			Add (tmp, 1ll * sum * fac[cnt - 1] % Mod);
/**/		if (cnt > 1) Add (tmp, Mod - (1ll * cnt * (cnt - 1) / 2 % Mod * tot1 % Mod * fac[cnt - 2] % Mod));
			if (cnt) Add (tmp, Mod - (1ll * tot2 * fac[cnt - 1] % Mod));
			++tot1;
		}
		Add (ans, 1ll * tmp * fac[N - i] % Mod);
	}
	cout<<ans<<endl;
	return 0;
}