HDU多校2020 第七场 E-Expectation（概率DP-算贡献的期望DP

题意：http://acm.hdu.edu.cn/showproblem.php?pid=6848

有n个小球，n+1个桶还有他们分别在数轴上的位置，交错排列，每次随机选一个小球往随机一个方向滚，遇到洞就掉下去，小球滚进洞后其他球可以在它上面溜过去。

问所有小球滚动距离的期望。

思路：

简单~（你tm在胡扯吧

具体还是有点复杂的。

题解是算每条边经过次数的期望，小球两边的线次数期望一定相同，洞两边的期望最多差1次，然后我们要算的是这条线到下一条线期望的增量，由于最多相差1次所以权值都是*1 or *-1 or *0，可以简单的记作加概率，也就是算右边球先进洞的概率减左边球先进洞的概率

首先第一条线题解是类似每次选一条线合并三条线，所以上面是（2*n-1）的双阶乘（一开始还以为是阶乘的阶乘||，太蒟蒻了）

然后我又想了一个n^2算a1的方法（太草了

本地卡在了4.9，后来用了读入挂过了

之后dp转移的话，大致就是每次你之间选洞两边的可以相互抵消，选其他相对于子问题

放上我的n^2算a1的代码

 1 ll qpow(ll a,ll b,ll mod){
 2     ll ans;
 3 //    a%=mod;
 4     ans=1;
 5     while(b!=0)
 6     {
 7         if(b&1)
 8             ans=(ans*a)%mod;
 9         b/=2;
10         a=(a*a)%mod;
11     }
12     return ans;
13 }
14 
15 ll a[N*2],er[N*2];
16 ll _[N*2];
17 ll _inv[N*2];
18 ll inv[N*2];
19 ll inv_ff[N*2];
20 
21 void Init(){
22     _[0]=_[1]=1;
23     er[0]=1;
24     for(int i=2;i<N*2;++i)_[i]=_[i-1]*i%mod;
25     for(int i=1;i<N*2;++i)er[i]=er[i-1]*2%mod;
26     for(int i=0;i<N*2;++i)inv_ff[i]=qpow(_[i]*er[i]%mod,mod-2,mod),_inv[i]=qpow(_[i],mod-2,mod);
27     for(int i=0;i<N*2;++i)inv[i]=qpow(i,mod-2,mod);
28 }
29 ll A(int n,int m){
30     return _[n+m]*_inv[n]%mod*_inv[m]%mod;
31 }
32 ll dis(int x,int y){
33     return llabs(a[x]-a[y])%mod;
34 }
35 ll F[N*2];
36 ll f(int n)
37 {
38     if(F[n])return F[n];
39     int res=0;
40     for(int i=2;i<=n;i+=2)
41     {
42         int X=i-2;
43         int Y=n-i;
44         res+=A(X/2+1,Y/2)*f(X)%mod*f(Y)%mod;
45         res%=mod;
46     }
47     F[n]=res;
48     return res;
49 }
50 
51 ll dp[N][N];
52 void pre()
53 {
54     int n=3003;
55     for(int i=1;i<=n;++i)
56     {
57         dp[0][i]=(1-f(i*2)*inv_ff[i]%mod+mod)%mod;
58         dp[i][0]=-dp[0][i];
59         //    cout << i << endl;
60         for(int j=1;j<i;++j)
61         {
62             int L=j,R=i-j;
63             dp[L][R]=((2*L-1)*dp[L-1][R]%mod+(2*R-1)*dp[L][R-1]%mod)%mod*inv[2*i]%mod;
64         }
65     }
66 }
67 
68 void solve()
69 {
70     int n;
71     cin>>n;
72     int real=n;
73     n=n*2+1;
74     for(int i=1;i<=n;++i)cin>>a[i];
75     ll ans=0;
76     ll res=0;
77     for(int i=1;i<=n-1;++i)
78     {
79         int L=(i-1)/2;
80         if(i&1)res=(res+dp[L][real-L])%mod;
81         ans+=res*dis(i,i+1)%mod;
82         ans%=mod;
83     }
84     cout<<(ans+mod)%mod;
85 }
86 
87 int main()
88 {
89     Init();
90     F[0]=1;
91     pre();
92     int T;
93     cin>>T;
94     while(T--)solve();
95     return 0;
96 }