「SOL」Social Distance(AtCoder)

由題意，設 $n$ 個動點的點集為 $\mathbb{P}$，相當于求 $$ E\Big(\min_{i,j\in \mathbb{P}}\{|x_i-x_j|\}\Big) $$

似乎由 min-max 反演，結合期望線性性可得下式：

$$ \sum_{\mathbb{S}\subset\mathbb{P}}(-1)^{|\mathbb{P}|-|\mathbb{S}|}E\Big(\max_{i,j\in\mathbb{S}}\{x_i-x_j\}\Big) $$

進而一個點集的最遠點距只與左右兩個點有關，于是可以快速地計算，但是看一眼 $n$ 的范圍，感覺哪里不對……但是哪里不對？

再觀察一下 min-max 反演的式子：

$$ \min_{x\in \mathbb{S}}\{x\}=\sum_{\mathbb{T}\subset\mathbb{S}}(-1)^{|\mathbb{S}|-|\mathbb{T}|}\max_{x\in\mathbb{T}}\{x\} $$

其實上述做法的誤區在于「集合」，這里求 min 的集合并不是點集 $\mathbb{P}$，而是點對集 $\{(i,j)\mid i,j\in\mathbb{P}\}$，于是列舉的子集也應該是點對集的子集，而列舉點對集的子集并不能簡化問題，

可以從離散隨機變數的期望計算式不嚴謹地證明上式，若離散隨機變數 $X$ 滿足其取值只可能是正數，則

$$ E(X)=\sum_{i=1}iP(X=i) $$

則必有 $E(x)=\sum_{i=1}P(x\ge i)$，從代數角度容易證明，而直觀也比較好理解——$P(x=i)$ 對期望的貢獻系數為 $i$，將系數 $i$ 均攤到 $1\sim i$ 上，每個位置分攤 $1$ 的系數，

而若是連續隨機變數（取值一定非負），我們仍有

$$ E(X)=\int_{0}^{+\infty}iP(X=i)\rm{d}i $$

依然考慮把 $P(X=i)$ 的系數 $i$ 均攤，那么既然是連續的，就要把系數分攤到區間 $(1,i)$ 上，每 $\rm di$ 分攤 $\rm di$ 的系數，得到結論，

/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
const int M=1e6+10,N=42,MOD=998244353;
const double EPS=1e-7;
#define con(type) const type &
inline int add(con(int)a,con(int)b){return a+b>=MOD?a+b-MOD:a+b;}
inline int sub(con(int)a,con(int)b){return a-b<0?a-b+MOD:a-b;}
inline int mul(con(int)a,con(int)b){return int(1ll*a*b%MOD);}
inline int ina_pow(con(int)a,con(int)b){return b?mul(ina_pow(mul(a,a),b>>1),(b&1)?a:1):1;}

int n;
int invi[M],posx[N];
double segl[N],segr[N];

struct Poly{
	vector<int> ary;
	Poly(){}
	Poly(con(int)x0){ary.push_back(x0);}
	Poly(con(int)x0,con(int)x1){ary.push_back(x0),ary.push_back(x1);}
	inline int degr()const{return (int)ary.size();}
	inline void extend(con(int)len){ary.resize(len);}
	inline int& operator [](con(int)i){return ary[i];}
	inline int operator [](con(int)i)const{return ary[i];}
	inline int calc(con(int)x)const{
		int ret=0;
		for(int nowx=1,i=0,ii=degr();i<ii;i++,nowx=mul(nowx,x))
			ret=add(ret,mul(ary[i],nowx));
		return ret;
	}
	inline int calcInt(con(int)le,con(int)ri)const{return sub(calc(ri),calc(le));}
	inline bool operator <(con(Poly)b)const{return degr()<b.degr();}
	friend Poly operator +(con(Poly)a,con(Poly)b){
		Poly c;c.extend(max(a.degr(),b.degr()));
		for(int i=0,ii=a.degr();i<ii;i++) c[i]=add(c[i],a[i]);
		for(int i=0,ii=b.degr();i<ii;i++) c[i]=add(c[i],b[i]);
		return c;
	}
	friend Poly operator -(con(Poly)a,con(Poly)b){
		Poly c;c.extend(max(a.degr(),b.degr()));
		for(int i=0,ii=a.degr();i<ii;i++) c[i]=add(c[i],a[i]);
		for(int i=0,ii=b.degr();i<ii;i++) c[i]=sub(c[i],b[i]);
		return c;
	}
	friend Poly operator *(con(Poly)a,con(Poly)b){
		Poly c;
		c.extend(a.degr()+b.degr()-1);
		for(int i=0,ii=a.degr();i<ii;i++)
			for(int k=0,kk=b.degr();k<kk;k++)
				c[i+k]=add(c[i+k],mul(a[i],b[k]));
		return c;
	}
	Poly getInt()const{
		Poly c;c.extend(degr()+1);
		for(int i=1,ii=c.degr();i<ii;i++)
			c[i]=mul(ary[i-1],invi[i]);
		return c;
	}
	void debug()const{
		for(int i=0,ii=degr();i<ii;i++) printf("%d ",ary[i]);
		printf("\n");
	}
}f[2][N<<1][N],fans;

pii vpos[N<<1];
vector< pair<double,Poly> > vdiv;
vector< pair<double,int> > tim_lis;

int ina_abs(con(int)x){return x<0?-x:x;}
double ina_abs(con(double)x){return x<0?-x:x;}
int sgn(con(double)x){
	if(ina_abs(x)<EPS) return 0;
	return x<0?-1:1;
}
void init(){
	invi[0]=1;
	for(int i=1;i<M;i++) invi[i]=mul(invi[i-1],i);
	invi[M-1]=ina_pow(invi[M-1],MOD-2);
	for(int i=M-2;i;i--){
		int nxt=mul(invi[i+1],i+1);
		invi[i+1]=mul(invi[i+1],invi[i]);
		invi[i]=nxt;
	}
}
//put i in [vdiv_j,vdiv_j+1]
Poly getPossi(con(int)i,con(int)j){
	if(sgn(vdiv[j+1].first-vdiv[j].first)<=0 || sgn(vdiv[j+1].first-segl[i])<=0 || sgn(segr[i]-vdiv[j].first)<=0)
		return Poly(0);
	return (vdiv[j+1].second-vdiv[j].second)*Poly(invi[posx[i+1]-posx[i]]);
}
int main(){
	// freopen("input.in","r",stdin);
	init();
	scanf("%d",&n);
	for(int i=0;i<=n;i++) scanf("%d",&posx[i]);
	for(int i=0;i<n;i++){
		vpos[i<<1]=make_pair(-i,posx[i]);
		vpos[i<<1|1]=make_pair(-i,posx[i+1]);
	}
	tim_lis.push_back(make_pair(0,0));
	tim_lis.push_back(make_pair(1e6,1000000));
	for(int i=0,icap=n<<1;i<icap;i++)
		for(int j=i+1;j<icap;j++){
			if(sgn(vpos[i].first-vpos[j].first)==0) continue;
			double tim=(double)(vpos[j].second-vpos[i].second)/(vpos[i].first-vpos[j].first);
			if(sgn(tim)<=0 || sgn(tim-1e6)>=0) continue;
			int vmod=mul(ina_abs(vpos[j].second-vpos[i].second),invi[ina_abs(vpos[i].first-vpos[j].first)]);
			tim_lis.push_back(make_pair(tim,vmod));
		}
	sort(tim_lis.begin(),tim_lis.end());
	int ans=0;
	for(int t=1,tt=(int)tim_lis.size();t<tt;t++){
		if(sgn(tim_lis[t].first-tim_lis[t-1].first)<=0) continue;
		vdiv.clear();
		double mi=(tim_lis[t].first+tim_lis[t-1].first)/2;
		for(int i=0;i<n;i++){
			segl[i]=posx[i]-i*mi;
			segr[i]=posx[i+1]-i*mi;
			vdiv.push_back(make_pair(segl[i],Poly(posx[i],sub(0,i))));
			vdiv.push_back(make_pair(segr[i],Poly(posx[i+1],sub(0,i))));
		}
		sort(vdiv.begin(),vdiv.end());
		int now=0;
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=n;k++)
				f[now][j][k].ary.clear();
		f[0][0][0]=Poly(1);
		for(int i=0;i<n;i++){
			for(int j=0;j<=2*n;j++)
				for(int k=0;k<=n;k++)
					f[now^1][j][k].ary.clear();
			for(int j=0,hj=(int)vdiv.size()-1;j<hj;j++)
				for(int k=0;k<n;k++){
					if(!f[now][j][k].degr()) continue;
					f[now^1][j][k+1]=f[now^1][j][k+1]+f[now][j][k]*getPossi(i,j)*Poly(invi[k+1]);
					f[now][j+1][0]=f[now][j+1][0]+f[now][j][k];
				}
			now^=1;
		}
		// printf("done");
		fans.ary.clear();
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=n;k++)
				fans=fans+f[now][j][k];
		ans=add(ans,fans.getInt().calcInt(tim_lis[t-1].second,tim_lis[t].second));
	}
	printf("%d\n",ans);
	return 0;
}