有趣的组合数学题；考试时候打满确实挺不容易的……
题目描述
对于一个 $n$ 阶排列 $p$，我们建立一张无向简单图 $G(p)$，有 $n$ 个节点，标号从 $1$ 到 $n$，每个点向左右两侧最近的比它大的点以及比它小的点连边。 形式化地，在 $G(p)$ 中，$forall u<v$，边 $(u,v)$ 存在当且仅当以下四个条件至少一个成立：
-
$p_u<p_v$，且不存在 $u<i<v$ 满足 $p_u<p_i$；
-
$p_u>p_v$，且不存在 $u<i<v$ 满足 $p_u>p_i$；
-
$p_u<p_v$，且不存在 $u<i<v$ 满足 $p_i<p_v$；
-
$p_u>p_v$，且不存在 $u<i<v$ 满足 $p_i>p_v$。
现在在所有的 $n$ 阶排列中随机选择一个排列 $p$，请求出 $G(p)$ 中三元简单环的期望个数，答案对 $998244353$ 取模。
数据规模与约定
对于所有数据，$1le n<998244353$。
题目分析
基础的暴力
首先会有个$(C^3_n)^2$的想法：枚举所有的三元环位置以及三个位置各是什么数，再根据这来统计每个三元环的合法贡献。
观察性质：从零开始推式子
提前透露一个模型：
$a+b+1=k, \, {nchoose k}=sum_i{i-1choose a}{n-ichoose b}$
感性理解来看相当于枚举一个中间点$i$并将它强制选取，再在它的两端钦定各选$a$,$b$个。这样就能有效地避免重复。
由于这题有非常特殊的建边性质，所以可以先来考虑怎么样形态的三元组才是合法的。
容易发现，三元环的极值一定是在中间点，那么就只存在四种形态的三元组。同时，这四种形态的三元环具有很好的对称性，所以它们方案数是相同的。
下面只考虑一种情况如上图所示。在这种情况下，想要三点间都存在边只能是能让$max a_{i...k} < a3$.
接下去从最暴力的式子开始推起：
$sum_{i=1}^{n-2}{n-ichoose2}sum_{k_1+k_2<i}{i-1choose k_1}{i-1-k_1choose k_2}k_1!k_2!(n-k_1-k_2-3)!(n-k_1-k_2-2)$
其中i表示枚举a1的取值；k1,k2表示a1...a3,a3...a2之间夹的数的个数。最后的一项$(n-k_1-k_2-2)$表示将i...k这些数看作一个整体，插空在其他数里的方案数。
然后将后面的组合数拆开：
$sum_{i=1}^{n-2}{n-ichoose2}sum_{k_1+k_2<i}{(i-1)!(n-k_1-k_2-2)!over (i-k_1-k_2-1)!}$
注意到这里变量$k_1+k_2$作为一个整体出现，所以可用$k$来代替：
$sum_{i=1}^{n-2}{n-ichoose2}sum_{k=0}^{i-1}{(i-1)!(n-k-2)!over (i-k-1)!}(k+1)$
最后项$k+1$是因为有$k+1$种$k_1+k_2=k$的方案。这一点比较细节。
接下去是换循环顺序和考虑组合数意义的环节：
$sum_{k=0}^{n-3}sum_{i=k+1}^{n-2}{(i-1)!over(i-k-1)!}(n-k-2)!(k+1){n-ichoose2}$
将无关$i$的变量提出，同时在外部乘$k!$来构造内部的组合数：
$sum_{k=0}^{n-3}(n-k-2)!(k+1)k!sum_{i=k+1}^{n-2}{(i-1)!over(i-k-1)!k!}{n-ichoose2}$
$sum_{k=0}^{n-3}(n-k-2)!(k+1)!sum_{i=k+1}^{n-2}{i-1choose k}{n-ichoose2}$
考虑这两个组合数相乘的实际意义。第一个相当于钦定选第$i$个数，再在前$i-1$个数里选出$k$个数；第二个相当于在剩下的$n-i$个数里再选出2个数。那么这一种限制就是上面提到的模型，即将$i$从$k+1$枚举到$n$的总和，相当于是在$n$个数中取出$k+3$个数的方案数。
因此式子可化成这个样子：
$sum_{k=0}^{n-3}(n-k-2)!(k+1)!{nchoose k+3}$
$n!sum_{k=0}^{n-3}{(n-k-2)!(k+1)!over(n-k-3)!(k+3)!}$
由于我们要求的是期望，那么就能把$n!$直接给去了。
$sum_{k=0}^{n-3}{n-(k+2)over(k+2)(k+3)}$
$sum_{k=2}^{n-1}{n-kover k(k+1)}$
$nsum_{k=2}^{n-1}{1over k(k+1)}-sum_{k=2}^{n-1}{1over k+1}$
对于前一项式子有：
$nsum_{k=2}^{n-1}{1over k(k+1)}=nsum_{k=2}^{n-1}[{1over k}-{1over (k+1)}]=n({1over 2}-{1over n})$
而后一项式子是经典的求自然数倒数和，解决方法是分段打表。
节略后的代码如下：
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 const int MO = 998244353; 4 const int seg[] = {0,227146302,963788543,596373246...}; //此处省略……65K 5 6 int n,fac,size,pos; 7 ll ans,cnt; 8 9 int qmi(int a, int b) 10 { 11 int ret = 1; 12 for (; b; b>>=1, a=1ll*a*a%MO) 13 if (b&1) ret = 1ll*ret*a%MO; 14 return ret; 15 } 16 int main() 17 { 18 scanf("%d",&n); 19 ans = (2*n-4)%MO, size = 150000; 20 pos = (n-2)/size, cnt = seg[pos]; 21 for (int i=1, mx=n-2-pos*size, sta=pos*size+2; i<=mx; i++) 22 cnt = 1ll*(cnt+qmi(sta+i, MO-2))%MO; 23 printf("%lld ",(ans-(cnt<<2)%MO+MO)%MO); 24 return 0; 25 }
END