【洛谷P5615】[MtOI2019]时间跳跃 | Mrsrz's blog

DP

题目大意：

给定长度为 $1\sim n$ 的 $n$ 条边。现在从中选边，每条边会等概率选或不选。

如果选定的 $k$ 条边能组成一个凸 $k$ 边形，那么它的贡献就为 $k$。

求贡献的期望。

题解：

$k(k>2)$ 条边能组成凸 $k$ 边形的充要条件是，其中最长的边的长度严格小于其他边的长度之和。

考虑对每条边，计算出这条边作为最大边时的贡献。我们通过总贡献减去不合法方案数的方式来计算。

令 $f_{i,j}$ 表示前 $i$ 条边，选择的边长和为 $j$ 的方案数，$g_{i,j}$ 表示前 $i$ 条边，选择的边长和为 $j$ 的所有方案的贡献之和。

转移的时候，考虑边 $i$ 选或者不选，容易得出 $f_{i,j}=f_{i-1,j}+f_{i-1,j-i}$。

$g_{i,j}$ 类似，不过对于 $g_{i-1,j-i}$ 的每一种情况，转移时都会产生额外的 $1$ 的贡献。

因此 $g_{i,j}=g_{i-1,j}+g_{i-1,j-i}+f_{i-1,j-i}$。

然后，从 $n$ 条边里任选的总贡献为：

$$\sum_{i=1}^ni\binom n i$$

这个可以 $O(n)$ 求出单个。

上述转移时，$j$ 这一维是 $n^2$ 级别的，但我们考虑的是不合法方案，所以每次只考虑不超过当前 $i$ 的，所以只需转移 $n$ 个即可。

所以时间复杂度 $O(n^2)$。可以通过打表进行优化。

空间的话，开两个 $n^2$ 的整形数组会超，所以滚动数组优化一下即可。

Code：

#include<iostream>
using namespace std;
const int md=1e9+7,N=5050,n=5000;
typedef long long LL;
int a[N],T,ans[N],f[2][N],g[2][N],_2[N],fac[N],iv[N];
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
    int ret=1;
    for(;b;b>>=1,a=(LL)a*a%md)
    if(b&1)ret=(LL)ret*a%md;
    return ret;
}
inline int C(int n,int m){return fac[n]*(LL)iv[m]%md*iv[n-m]%md;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    f[0][0]=1;
    for(int i=_2[0]=1;i<=n;++i)_2[i]=(_2[i-1]<<1)%md;
    for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
    iv[n]=pow(fac[n],md-2);
    for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n;++j)
        f[i&1][j]=f[i&1^1][j],g[i&1][j]=g[i&1^1][j];
        for(int j=i;j<=n;++j)
        upd(f[i&1][j]+=f[i&1^1][j-i]-md),
        g[i&1][j]=(g[i&1][j]+(LL)g[i&1^1][j-i]+f[i&1^1][j-i])%md;
        ans[i]=_2[i-1];
        for(int j=1;j<i;++j)
        ans[i]=(ans[i]+(LL)j*C(i-1,j))%md;
        for(int j=0;j<=i;++j)
        upd(ans[i]-=g[i&1^1][j]),upd(ans[i]-=f[i&1^1][j]);
    }
    for(int i=1;i<=n;++i)upd(ans[i]+=ans[i-1]-md);
    for(cin>>T;T--;){
        int n;
        cin>>n;
        cout<<(ans[n]*(LL)pow(_2[n],md-2))%md<<'\n';
    }
    return 0;
}