流浪者(rover)

题目描述

有一位流浪者正在一个n∗mn∗m的网格图上流浪。初始时流浪者拥有SS点体力值。

流浪者会从(1,1)(1,1)走向(n,m)(n,m),并且他只会向下走((x,y)→(x+1,y))((x,y)→(x+1,y))或是往右走((x,y)→(x,y+1))((x,y)→(x,y+1)),在所有可行的路线中他会随机选择一条。

网络图中还有KK个障碍点。若流浪者当前体力值为SS，则他经过一个障碍点后体力值会变为⌈S2⌉⌈S2⌉。

现在请你求出，流浪者到达(n,mn,m)时他体力值的期望是多少。

若答案为abab,则你输出abab在模109+7109+7意义下的值即可。

输入

第一行四个整数n,m,K,Sn,m,K,S, 意义见题目描述。

接下来K行每行两个整数Xi,YiXi,Yi,表示一个障碍点，保证一个障碍点不会出现多次。起点与终点可能也会是障碍点。

输出

仅一行一个整数表示答案。

样例1解释

共有6种合法路径，这里不一一列出。

16∗(6+6+11+3+6+6)=19316∗(6+6+11+3+6+6)=193

约定

30%的数据：n,m≤10n,m≤10

50%的数据：n,m≤1000n,m≤1000

1000%的数据：1≤n,m≤105,0≤K≤min(n∗m,2000),1≤S≤1061≤n,m≤105,0≤K≤min(n∗m,2000),1≤S≤106

solution

slz：经典模型

我：完全不会

30：dfs

50:dp 令f[i][j][k]表示走到i j，经过k个格子的方案数

由于当k>20时对k不同对答案没有影响，最后一维可以只开20

O(nm20)

100:

dp 令f[i][j]表示当前在第i个特殊点，走到终点还会经过恰好j个特殊点的路径数

g[i][j]表示当前在第i个特殊点，走到终点还会经过小于等于j个特殊点的路径数

$f[i][j]=g[i][j]-g[i][j-1]$

$g[i][j]=ways(i,n)-ways(i,k)*f[i][k]$

ways（i,j）表示i到j的路径数

从后往前dp即可

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define maxn 2005

#define mod 1000000007

#define ll long long

using namespace std;

int n,m,K,S,s[24];

ll h[200008],ny[200008],f[maxn][25],g[maxn][23];

ll work(ll a,int num){

    ll ans=1;

    while(num){

        if(num&1)ans=ans*a;

        a=a*a;a%=mod;ans%=mod;num>>=1;

    }

    return ans;

}

struct node{

    int x,y;

}p[maxn];

bool cmp(node a,node b){

    return a.x<b.x||a.x==b.x&&a.y<b.y;

}

ll C(int N,int M){

    return h[N]*ny[M]%mod*ny[N-M]%mod;

}

int main()

{

    cin>>n>>m>>K>>S;

    int Max=200005;h[0]=1;

    for(int i=1;i<=Max;i++)h[i]=h[i-1]*i%mod;

    ny[Max]=work(h[Max],mod-2);

    for(int i=Max-1;i>=0;i--)ny[i]=ny[i+1]*(i+1)%mod;

    s[0]=S;int cnt=0;

    for(;s[cnt]>1;cnt++)s[cnt+1]=(s[cnt]+1)/2;

    for(int i=1;i<=K;i++){

        scanf("%d%d",&p[i].x,&p[i].y);

    }

    sort(p+1,p+K+1,cmp);

    p[0].x=1;p[0].y=1;

    for(int i=K;i>=0;i--){

        int xi=p[i].x,yi=p[i].y;

        for(int j=0;j<cnt;j++){

            ll sum=0;g[i][j]=C(n-xi+m-yi,n-xi);

            for(int k=K;k>i;k--){

                if(p[k].y<p[i].y)continue;

                int xk=p[k].x,yk=p[k].y;

                sum+=f[k][j]*C(xk-xi+yk-yi,xk-xi)%mod;

                sum%=mod;

            }

            g[i][j]-=sum;g[i][j]%=mod;

        }

        g[i][cnt]=C(n-xi+m-yi,n-xi);

        for(int j=1;j<=cnt;j++)f[i][j]=(g[i][j]-g[i][j-1])%mod;

        f[i][0]=g[i][0];

    }

    ll Answer=0;

    for(int i=0;i<=cnt;i++){

        Answer+=f[0][i]*s[i]%mod;

        Answer%=mod;

    }

    ll All=C(n+m-2,m-1);

    Answer=Answer*work(All,mod-2);

    Answer=(Answer%mod+mod)%mod;

    printf("%lld\n",Answer);

    return 0;

}

巴特西

流浪者(rover)

流浪者(rover)

题目描述

输入

输出

最新文章

热门文章