题解 CF722E 【Research Rover】

题解- CF722E

题目意思

题目就是让你从 $(1,1)$ 走到 $(n,m)$ 的道路中有 $k$ 个特殊点，没经过一个特殊点会使分数变为原来一半，问从 $(1,1)$ 到 $(n,m)$ 的期望得分（对 $10^9+7$ 取模）
$Sol$

我们首先把 $(1,1),(n,m)$ 也看成特殊点，但是分数不用除二，然后为了保证每次是向下或向右先对 $x$ 排序即可，接下来就是 $Dp$ 啦。

这道题目如果把状态设为 $f_{i,j}$ 表示到 $i$ 点经过 $j$ 个特殊点的方案数的话，转移就很麻烦了。所以我们把状态改为 $f_{i,j}$ 表示表示到 $i$ 点至少经过 $j$ 个特殊点的方案数，这样就可以避免一些很麻烦的容斥。

然后我们再设 $g_{i,j}$ 表示从 $i$ 到 $j$ 点的方案数，那么这就变为一个清新的组合数问题，我们考虑一共走了 $(i+j)$ 次，最后选 $i$ 次向上，所以

$g_{i,j}=C^{|x_i-x_j|}_{|x_i-x_j|+|y_i-y_j|}$

对于 $f_{i,j}$ 的转移我们考虑从 $j-1$ 转移过来，这里很好的体现状态设计的正确性，我们计算正好 $j$ 次，所以

$f_{i,j}=\sum f_{k,j-1}-f_{k,j}(x_k\leq x_i,y_k\leq y_i)$

其中 $(f_{k,j-1}-f_{k,j})$ 表示经过 $j-1$ 个特殊点到达 $i$ 的方案数。

那么最后的答案就是 $(C^{n}_{n+m})$ $^{-1} \times \sum(f_{k,i}-f_{k,i+1}) \times (s/2^{i})$

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int mod=1e9+7;
const int N=1e5+5;

inline int ksm(int x,int y)
{
    int ret=1ll;
    while(y)
    {
        if(y&1) ret=ret*x%mod;
        x=x*x%mod;
        y>>=1ll;
    }
    return ret;
}

int n,m,s,k,f[N][31],ans,jc[N*2],inv[N*2];

struct nood
{
    int x,y;
    inline bool friend operator < (const nood &b,const nood &c)
    {
        if(b.x==c.x) return b.y<c.y;
        return b.x<c.x;
    }
};
nood a[N];

inline int C(int x,int y)
{
    return jc[x]%mod*inv[x-y]%mod*inv[y]%mod;
}

inline int calc(nood b,nood c)
{
    return C(c.x-b.x+c.y-b.y,c.x-b.x);
}

signed main()
{
    n=read();
    m=read();
    k=read();
    s=read();
    inv[0]=jc[0]=1;
    for ( int i=1;i<=n+m;i++ ) jc[i]=jc[i-1]*i%mod;
    for ( int i=1;i<=n+m;i++ ) inv[i]=ksm(jc[i],mod-2)%mod;
    for ( int i=1;i<=k;i++ ) a[i]=(nood){read(),read()};
    sort(a+1,a+k+1);
    if(a[1].x!=1||a[1].y!=1) 
    {
        a[++k]=(nood){1,1};
        s*=2;
    }
    if(a[k].x!=n||a[k].y!=m) a[++k]=(nood){n,m};
    //加入虚拟点(1,1)/(n,m) 
    else s=(s+1)/2;
    int gs=log2(s)+1;
    //最多经过gs个特殊点 
    sort(a+1,a+k+1);
    f[1][0]=1;
    //f(i,j)：到点i经过（至少）j个特殊点的方案数 
    for ( int i=2;i<=k;i++ )
    {
        f[i][1]=calc(a[1],a[i]);
        for ( int j=2;j<=gs;j++ )
            for ( int t=1;t<i;t++ ) 
                if(a[t].x<=a[i].x&&a[t].y<=a[i].y)
                {
                    f[i][j]+=(f[t][j-1]*calc(a[t],a[i]))%mod;
                    f[i][j]=(f[i][j]+mod)%mod;
                    f[i][j]-=(f[t][j]*calc(a[t],a[i]))%mod;
                    f[i][j]=(f[i][j]+mod)%mod;
                }
    }
    int ans=0;
    for ( int i=1;i<=gs;i++ ) 
    {
        s-=s/2;
        ans=(ans+(f[k][i]-f[k][i+1])*s%mod+mod)%mod;
    }
    ans=(ans*ksm(calc(a[1],a[k]),mod-2)+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}
/*
3 3 2 11
2 1
2 3
*/