[HDU-6848] Expectation (2020多校7T5) (dp)

Posted on Edited on In

[HDU-6848] Expectation (2020多校7T5) (dp)

比赛时疯狂脑抽写了3个小时祭

考虑计算每条 \(x_i\rightarrow x_{i+1}\) 的边被在所有情况下被经过的次数总和

令 \(dp[i][j]\) 为有 \(i\) 个球时， \(x_j\rightarrow x_{j+1}\) 这段被经过的次数总和( \(j\leq 2i\) )

考虑转移，对于 \(dp[i]\) ，枚举每个球向左或者右走，发现把两边的部分拉拢过来后，合并形成一条包含了原先 \(3\) 条边的新边，变成了 \(i-1\) 阶的子问题

画图理解，发现 \(j\) 这条边，在 \(i-1\) 阶的子问题上对应的编号只可能是 \(j,j-1,j-2\)

视选择了 \(j\) 这条边为将边一端的球滚进另一端的洞里

那么对于任意一条编号为 \(j\) 的边

\(j\) 变为编号为 \(j-2\) 的情况为选择了编号 \([1,j-1]\) 范围内的边

\(j\) 变为编号为 \(j-1\) 的情况为选择了编号为 \(j\) 的边

\(j\) 变为编号为 \(j\) 的情况为选择了编号为 \([j+1,2i]\) 的边

对于 \(j\) 在子问题中被访问的次数可以直接 \(O(1)\) 继承过来

同时，考虑当第一次就选了 \(j\) 时，后面的操作随意，即加上 \((i-1)!\cdot 2^{i-1}\)

于是得到一个 \(O(n^2)\) 的 \(dp\) 预处理

而对于每个询问，求解 \(n\) 阶的答案复杂度为 \(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=3010,P=998244353;

int n;
int dp[N][N*2],Fac[N];
ll qpow(ll x,ll k=P-2) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}

int main(){
    rep(i,Fac[0]=1,N-1) Fac[i]=1ll*i*Fac[i-1]%P;
    dp[1][1]=dp[1][2]=1;
    int t=1;
    rep(i,2,N-1) {
        t=1ll*t*(i-1)*2%P;
        rep(j,1,i*2) {
            dp[i][j]=(1ll*(i*2-j)*dp[i-1][j]+1ll*dp[i-1][j-1]+1ll*(j-1)*(j>=2?dp[i-1][j-2]:0)+t)%P;
        }
    }

    rep(kase,1,rd()) {
        n=rd();
        int ans=0,x=rd();
        rep(i,1,n*2) {
            int y=rd();
            ans=(ans+1ll*(y-x)*dp[n][i])%P;
            x=y;
        }
        ans=ans*qpow((P+1)/2,n)%P*qpow(Fac[n])%P;
        printf("%d\n",ans);
    }
}