题解 CF722E 【Research Rover】

题解- CF722E

• 题目意思

  题目就是让你从走到的道路中有个特殊点，没经过一个特殊点会使分数变为原来一半，问从到的期望得分（对取模）

• 

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

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

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

  

  对于的转移我们考虑从转移过来，这里很好的体现状态设计的正确性，我们计算正好次，所以

  

  其中表示经过个特殊点到达的方案数。

  那么最后的答案就是

#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
*/