题解 \(by\;zj\varphi\)
概率与期望，考虑 \(\rm dp\)
设 \(dp_{i,j}\) 为消除 \(i～j\) 这一段行星的期望，转移：
枚举 \(k\) 为当前状态下第一个撞击的行星，分向左，向右。
\[\rm dp_{i,j}=\sum_{k=i}^jdp_{i,k-1}+dp_{k+1,i}+E_{k+1,j}-pos_k \] \[\rm dp_{i,j}=\sum_{k=i}^jdp_{i,k-1}+dp_{k+1,i}-E_{i,k-1}+pos_k \]\(\rm E_{i,j}\) 表示 \(\rm i->j\) 的期望位置，转移与 \(\rm dp\) 类似。
这样就可以 \(\mathcal O\rm (n^3)\)，加个前缀和即可优化成 \(\mathcal O\rm(n^2)\)
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf,OPUT[100];
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++;
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
template<typename T>inline void print(T x,char t) {
if (x<0) putchar('-'),x=-x;
if (!x) return putchar('0'),(void)putchar(t);
ri cnt(0);
while(x) OPUT[p(cnt)]=x%10,x/=10;
for (ri i(cnt);i;--i) putchar(OPUT[i]^48);
return (void)putchar(t);
}
}
using IO::read;using IO::print;
namespace nanfeng{
#define int long long
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=3e3+7,MOD=998244353;
int dp[N][N],suf[N][N],pre[N][N],ex[N][N],a1[N][N],a2[N][N],inv[N],pa[N],n;
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
read(n);
inv[1]=1;
ri al=(n<<1)+1;
for (ri i(2);i<=al;p(i)) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
for (ri i(1),pla;i<=n;p(i)) {
read(ex[i][i-1]),read(pla);
pa[i]=(pa[i-1]+pla)%MOD;
}
read(ex[n+1][n]);
for (ri i(n);i;--i)
for (ri j(i);j<=n;p(j)) {
pre[i][j]=(pre[i][j-1]+ex[i][j-1])%MOD;
suf[j][i]=(suf[j][i+1]+ex[i+1][j])%MOD;
ex[i][j]=(pre[i][j]+suf[j][i])*inv[j-i+1]%MOD*inv[2]%MOD;
dp[i][j]=(dp[i][j]+2*(a1[i][j-1]+a2[j][i+1])%MOD)%MOD;
dp[i][j]=(dp[i][j]+pa[j]-pa[i-1]-pre[i][j])%MOD;
dp[i][j]=(dp[i][j]-pa[j]+pa[i-1]+suf[j][i])%MOD;
dp[i][j]=dp[i][j]*inv[j-i+1]%MOD*inv[2]%MOD;
a1[i][j]=(a1[i][j-1]+dp[i][j])%MOD;
a2[j][i]=(a2[j][i+1]+dp[i][j])%MOD;
}
print((dp[1][n]+MOD)%MOD,'\n');
return 0;
}
#undef int
}
int main() {return nanfeng::main();}