ARC花式掉分
# 题面
数轴上从左到右给出 (n+1) 个不重叠的点 (x_0,x_1,cdots,x_n)；另有 (n) 个动点 (y_0,y_1,cdots,y_{n-1})，其中 (forall i,y_iin(x_i,x_{i+1}))。
若每个 (y_i) 落在其取值范围内的每个位置概率相等，求「动点两两之间的最小距离」的期望，对 (998244353) 取模。
数据规模 (1le nle20)。
# 解析
看到求最小距离可能会先想到 min-max 反演 转化成最大距离（虽然我连这个都没有想到），但是这个想法是不可行的。
点击展开/折叠 此题「min-max反演」的误区
由题意，设 $n$ 个动点的点集为 $mathbb{P}$，相当于求 $$ EBig(min_{i,jin mathbb{P}}{|x_i-x_j|}Big) $$
似乎由 min-max 反演，结合期望线性性可得下式：
$$ sum_{mathbb{S}subsetmathbb{P}}(-1)^{|mathbb{P}|-|mathbb{S}|}EBig(max_{i,jinmathbb{S}}{x_i-x_j}Big) $$
进而一个点集的最远点距只与左右两个点有关，于是可以快速地计算。但是看一眼 $n$ 的范围，感觉哪里不对……但是哪里不对？
再观察一下 min-max 反演的式子：
$$ min_{xin mathbb{S}}{x}=sum_{mathbb{T}subsetmathbb{S}}(-1)^{|mathbb{S}|-|mathbb{T}|}max_{xinmathbb{T}}{x} $$
其实上述做法的误区在于「集合」，这里求 min 的集合并不是点集 $mathbb{P}$，而是点对集 ${(i,j)mid i,jinmathbb{P}}$。于是枚举的子集也应该是点对集的子集，而枚举点对集的子集并不能简化问题。
转化成相邻两点的最小距离。设相邻两点的最小距离为 (t)，则下式成立：
点击折叠/展开「关于上式」
可以从离散随机变量的期望计算式不严谨地证明上式，若离散随机变量 $X$ 满足其取值只可能是正数，则
$$ E(X)=sum_{i=1}iP(X=i) $$
则必有 $E(x)=sum_{i=1}P(xge i)$。从代数角度容易证明，而直观也比较好理解——$P(x=i)$ 对期望的贡献系数为 $i$，将系数 $i$ 均摊到 $1sim i$ 上，每个位置分摊 $1$ 的系数。
而若是连续随机变量（取值一定非负），我们仍有
$$ E(X)=int_{0}^{+infty}iP(X=i) m{d}i $$
依然考虑把 $P(X=i)$ 的系数 $i$ 均摊，那么既然是连续的，就要把系数分摊到区间 $(1,i)$ 上，每 $ m di$ 分摊 $ m di$ 的系数，得到结论。
先不考虑别的，假如给定最小距离 (d)，应该如何求解 (P(tge d))？
根据题意，有下式：
那么设 (y'_i=y_i-it)，则有 (y'_{i+1}ge y_i')，(y_i'inig(x_i-it,x_{i+1}-itig))。
这一步转化非常重要。
但是由于变量是连续的，我们不可能直接决策每个变量的具体的值，而是决定每个变量落在哪个范围内。
(n) 对形如 (x_i-it,x_{i+1}-it) 的点将 (y'_i) 可能存在的区间划分成 (2n-1) 段。我们把这 (2n-1) 个段依次编号为 (0sim 2n-2)，可以预先求得 (y_i') 可能落在的段的编号范围，记为 ([l_i,r_i])。
然后我们就可以设计一个 DP —— (f(i,j,k)) 表示 (y_i') 落在第 (j) 段内，此时第 (j) 段中已有 (k) 个变量。
那么 (y_i') 要么和 (y_{i-1}') 落在同一个段内，要么落在之后的段内。
考虑由 (f(i-1,j,k)) 转移到下一个值：
- 若 (y_i') 与 (y_{i-1}') 落在同一个段：则先前落在段 (j) 内的点把第 (j) 段划分成 (k+1) 小段，而 (y_i') 只能落在最后一小段，因此概率除以 (k+1)，再乘上 (y_i') 落在第 (j) 段的概率 (P(i,j))，则[f(i,j,k+1):=f(i,j,k+1)+frac{f(i-1,j,k)P(i,j)}{k+1} ]
- 若 (y_i') 落在之后的段中[f(i,j',1):=f(i,j',1)+f(i-1,j,k)P(i,j) ]
令段 (j) 的长度为 (L_j)，(y'_i) 可能的取值范围长度为 (D_i)；那么 (P(i,j)=frac{L_j}{D_i})。我们发现 (D_i) 是一个常值，而 (L_j) 是关于 (t) 的一个一次多项式。
第二种转移可以前缀和优化，于是可以在 (O(n^3R)) 的复杂度内完成整个DP，(R) 是单次转移的复杂度。
于是可以推得 (f(n-1,j,k)) 是关于 (t) 的 (n) 次多项式。单词转移要么是对多项式乘以一个常数，要么是一个一次多项式与另一个多项式相乘，那么单次转移复杂度 (R=n)。
所以 DP 的复杂度为 (O(n^4))。
再看看怎么求答案，不可能直接枚举 (t)，那么一定也是 (t) 的一个取值范围一起计算答案。由于我们可以 DP 求得 (f(n,j,k)) 关于 (t) 的多项式，如果知道 (t) 的对应范围，就可以通过定积分求解期望。
不难注意到，只要 (2n) 个点 (x_i-it,x_{i+1}-it) 的大小顺序不变，则最后得到的 (f(n-1,j,k)) 关于 (t) 的表达式就不会变。
所以对每一种点的顺序，都要计算一次 DP。
最后一个问题，一共有多少种点的顺序？答案是 (O(n^2))。注意到点的平移速度不同，但对于同一个点，其平移速度是常数，所以最初靠后的点 (A) 平移超过最初靠前的一个点 (B) 后（(A) 的平移速度大于 (B)），(A) 就一直在 (B) 前面。只会发生 (O(n^2)) 次点的相对位置变化。
# 源代码
点击展开/折叠代码
/*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("
");
}
}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
",ans);
return 0;
}