Loj 552 MIN&MAX I

Posted on | Views:

分段打表.

考虑 $3$ 个位置 $i<j<k$ 能形成三元环,需要满足

  • $p_j>\max(p_i,p_k)$ ,且区间 $(i,j),(j,k)$ (如果有) 中的数都 $>p_j$ .

或

  • $p_j<\min(p_i,p_k)$ ,且区间 $(i,j),(j,k)$ (如果有) 中的数都 $<p_j​$ .

两种情况是对称的,只需要算第一种情况的贡献,最后将答案乘上 $2$ .

考虑给出一个排列 $p $ ,某个位置 $j$ 能产生 $1$ 的贡献,当且仅当 $p_j$ 既不是前缀最小值,也不是后缀最小值.

这个概率为 $1-\frac{1}{j}-\frac{1}{n-j+1}+\frac{1}{n}$ .

即所有的减去它是前缀最小值的概率,减去它是后缀最小值的概率,加上同时是最小值的概率.

于是得到答案为
$$
\begin{aligned}
ans&=2\cdot\sum_{i=1}^n (1-\frac{1}{i}-\frac{1}{n-i+1}+\frac{1}{n}) \\
&=2\cdot(n+1-2\cdot \sum_{i=1}^n \frac{1}{i})
\end{aligned}
$$
只需要快速求出 $\sum_{i=1}^n \frac 1 i$ ,分段打表即可.

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
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int K=1e6;
void gen()
{
	freopen("data.out","w",stdout);
	printf("0,");
	int sum=0;
	for(int i=1;i<P;++i)
	{
		inc(sum,fpow(i,P-2));
		if(i%K==0)
		{
			printf("%d,",sum);
			cerr<<i<<endl;
		}	
	}
	puts("");
}
const int sum[]={};
int calc(int n)
{
	int res=sum[n/K];
	for(int i=n/K*K+1;i<=n;++i)
		inc(res,fpow(i,P-2));
	return add(res,res);
}
int main()
{
	int n=read();
	int ans=n+1;
	inc(ans,P-calc(n));
	inc(ans,ans);
	cout<<ans<<endl;
	return 0;
}