[unknown OJ] 客星璀璨之夜
一、題目
二、解法
這個樣例我佛了，第二個等差數列，第三個等等差數列，沒把我考試的錯誤測出來。
直接講正解，設 d p [ i ] [ j ] dp[i][j] dp[i][j]為行星 i i i到 j j j，把他們撞完的期望距離和，理解一下這個狀態，首先一定會剩下一個恆星，記第 i i i行星左邊的恆星是 i i i，這樣無論怎麼撞都不會撞出恆星 [ i , j + 1 ] [i,j+1] [i,j+1]
考慮轉移，我們嚴格按照題目要求進行，列舉當前狀態下第一個去撞擊的行星，列舉他往左邊撞還是右邊撞，這樣就產生了
2
(
j
−
i
+
1
)
2(j-i+1)
2(j−i+1)種等概率的情況，這是左邊的情況：
d
p
[
i
]
[
j
]
=
d
p
[
i
]
[
k
−
1
]
+
d
p
[
k
+
1
]
[
j
]
+
y
[
k
]
−
E
[
i
]
[
k
−
1
]
dp[i][j]=dp[i][k-1]+dp[k+1][j]+y[k]-E[i][k-1]
dp[i][j]=dp[i][k−1]+dp[k+1][j]+y[k]−E[i][k−1]這是右邊的情況：
d
p
[
i
]
[
j
]
=
d
p
[
i
]
[
k
−
1
]
+
d
p
[
k
+
1
]
[
j
]
+
E
[
k
+
1
]
[
j
]
−
y
[
k
]
dp[i][j]=dp[i][k-1]+dp[k+1][j]+E[k+1][j]-y[k]
dp[i][j]=dp[i][k−1]+dp[k+1][j]+E[k+1][j]−y[k]其中
E
[
i
]
[
j
]
E[i][j]
E[i][j]是
[
i
,
j
]
[i,j]
[i,j]中期望剩下來的位置，轉移（左還是右，等概率）：
E
[
i
]
[
j
]
=
E
[
i
]
[
k
−
1
]
+
E
[
k
+
1
]
[
j
]
2
(
j
−
i
+
1
)
E[i][j]=\frac{E[i][k-1]+E[k+1][j]}{2(j-i+1)}
E[i][j]=2(j−i+1)E[i][k−1]+E[k+1][j]注意
E
[
i
+
1
]
[
i
]
E[i+1][i]
E[i+1][i]是有意義的，他表示第
i
+
1
i+1
i+1個恆星的位置，暴力做時間複雜度是
O
(
n
3
)
O(n^3)
O(n3)的，觀察發現好像可以用字首和之類的東西優化，所以時間複雜度
O
(
n
2
)
O(n^2)
O(n2)
還有另一種思路，沒有實現，但是貼一個講解
貼一個巨佬的部落格，好像講了這種做法：https://www.cnblogs.com/Arextre/p/13775589.html
#include <cstdio>
const int M = 3005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') f=-1;
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,inv[M],x[M],y[M],py[M],dp[M][M],E[M][M];
int s1[M][M],s2[M][M],pre[M][M],suf[M][M];
signed main()
{
//freopen("3.in","r",stdin);
//freopen("stars.out","w",stdout);
n=read();
inv[0]=inv[1]=1;
for(int i=2;i<=n+1;i++)
inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i=1;i<=n;i++)
{
x[i]=read();
y[i]=read();py[i]=(py[i-1]+y[i])%MOD;
}
x[n+1]=read();
E[1][0]=x[1];
for(int i=1;i<=n;i++)
E[i+1][i]=x[i+1];
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++)
{
/*
for(int k=i;k<=j;k++)
{
E[i][j]=(E[i][j]+(E[i][k-1]+E[k+1][j])*inv[2])%MOD;
dp[i][j]=(dp[i][j]+2*(dp[i][k-1]+dp[k+1][j]))%MOD;
dp[i][j]=(dp[i][j]+y[k]-E[i][k-1])%MOD;
dp[i][j]=(dp[i][j]+E[k+1][j]-y[k])%MOD;
}
E[i][j]=E[i][j]*inv[j-i+1]%MOD;
dp[i][j]=dp[i][j]*inv[j-i+1]%MOD*inv[2]%MOD;
*/
pre[i][j]=(pre[i][j-1]+E[i][j-1])%MOD;
suf[j][i]=(suf[j][i+1]+E[i+1][j])%MOD;
E[i][j]=(pre[i][j]+suf[j][i])*inv[j-i+1]%MOD*inv[2]%MOD;
dp[i][j]=(dp[i][j]+2*(s1[i][j-1]+s2[j][i+1]))%MOD;
dp[i][j]=(dp[i][j]+(py[j]-py[i-1])-pre[i][j])%MOD;
dp[i][j]=(dp[i][j]+suf[j][i]-(py[j]-py[i-1]))%MOD;
dp[i][j]=dp[i][j]*inv[j-i+1]%MOD*inv[2]%MOD;
s1[i][j]=(s1[i][j-1]+dp[i][j])%MOD;
s2[j][i]=(s2[j][i+1]+dp[i][j])%MOD;
}
printf("%lld\n",(dp[1][n]+MOD)%MOD);
}