Codeforces Round #680 (Div. 1)

B.

我感觉这题很精彩，主要有两个点：

1.首先是一个结论，就是分割方式不影响最后这段求和后的f。先把a数组排序，前半段属于L，后半段属于R， |qi-pi|,必然一个数属于L，一个数属于R，于是求和的时候就可以前半段的数取负数，后半段的数取正数，相加求和。

这个证明如下，反证法，不妨设两个都属于前半段。

设下标小于pi的数有px个，下标大于qi的有qx个，px=n,无论如何这两个数都碰不上面，产生矛盾。也可以看cf的官方题解。

2.就是O(n)求逆元,学习√

综上最后答案ans=一段求和C[2n][n];

/*
O(n)求1-n逆元：前提：p是素数
inv[i]=(p-p/i)*inv[p%i]%p
prove. Let t=p/i,k=p%i
t*i+k=0 (mod p)
-t*i =k(mod p)
两边同除以ik，-t*inv[k]=inv[i] (mod p)
因此 inv[i]=(p-t)*inv[k] (mod p)
*/
 fac[0]=1;for(int i=1;i

#include
using namespace std;
typedef long long ll;
const int maxn=4e6+100;
const int mod=998244353;
ll n,a[maxn],fac[maxn],inv[maxn];
#define debug(x) cout<<#x<<':'<