NOIP 模拟 $28\; \rm 客星璀璨之夜$

题解 $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();}

巴特西

NOIP 模拟 $28\; \rm 客星璀璨之夜$

题解 \(by\;zj\varphi\)

最新文章

热门文章