[Codeforces 722E]Research Rover

guoyangfan 2019-07-24 原文

题目大意：

给出一个n*m的方格阵，从(1,1)走到(n,m)，只能向下或向右走，(1,1)会有一个初始分数s。在整个图中有k个特殊点，每经过一个点，都会将目前剩余的分数除以2且向上取整。求(1,1)到(n,m)的期望得分。

1<=n,m<=1e5;0<=k<=2000;1<=s<=1e6;

DP+容斥。

要求期望就好好求嘛，反正我看不懂某篇题解为什么答案只算经过k个特殊点的方案数
由于n,m<=1e5，显然不能暴力枚举点,yy出复杂度不含n、m. ,所以我们可以枚举特殊点。
仔细分析，发现当k>log₂s的时候s到(n,m)的值就为1了。所以最多枚举20个特殊点左右。
枚举特殊点就要将特殊点排序，那么就以横坐标为第一关键字，以纵坐标为第二关键字。
然后就容斥搞啊
倒着来。
噢还有，这道题要卢卡斯定理、逆元。

　　令d[i][j]表示从点i走到点j的方案总数，根据小学组合数我们可以知道d[i][j] = C(a[j].x-a[i].x+a[j].y-a[j].x , a[j].x – a[i].x)

设g[i][j]表示从点i到(n,m)恰好经过j个障碍点（不包括点i）的方案数。

显然很难求。那么我们添加一个辅助变量，f[i][j]表示从点i到点(n,m)至少经过j个点的方案数。

所以f数组的求法就是将总数减去超过j个点的方案数。

f[i][j] = d[i][(n,m) – ∑(g[k][j]*d[i][k]),满足a[k].x >= a[i].x,a[k].y>=a[i].y;

所以,g[i][j] =f[i][j] – f[i][j-1]。

有点类似与前缀和。

代码里合并在一起了。

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

const int mod = 1000000007;
const int maxn = 2e5+5;

int a[30],fac[maxn],ine[maxn],g[maxn][30];

struct node{
    int x,y;
}e[3000];

bool cmp(node a,node b){
    return a.x == b.x?a.y < b.y:a.x < b.x;
}

int C(int x,int y){
    return 1ll * fac[x]*ine[y]%mod*ine[x-y]%mod;
}

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

int main(){
    int n,m,k,s;
    cin>>n>>m>>k>>s;
    fac[0] = 1;
    for(int i = 1;i<=n+m;++i)fac[i] = 1ll*fac[i-1]*i%mod;
    ine[n+m] = qpow(fac[n+m],mod-2);
    for(int i = n+m;i>=1;--i)ine[i-1] = 1ll*ine[i]*(i)%mod;
    int len = 0;a[0] = s;
    for(len = 1;s != 1;len++)a[len] = s = (s+1)/2;
    len--;
    for(int i = 1;i<=k;++i)cin>>e[i].x>>e[i].y;
    sort(e+1,e+k+1,cmp);e[0].x = e[0].y = 1;
    for(int i = k;i>=0;--i){
        for(int j = 0;j<len;++j){
            g[i][j] = C(n-e[i].x+m-e[i].y,n-e[i].x);
            for(int l = k;l>i;--l){
                if(e[i].y <= e[l].y){
                    g[i][j] = (g[i][j]-1ll*g[l][j]*C(e[l].x-e[i].x+e[l].y-e[i].y,e[l].x-e[i].x))%mod;
                }
            }
        }//上面的g数组相当于f数组。
        g[i][len] = C(n-e[i].x+m-e[i].y,n-e[i].x);
        for(int j = len;j>=1;--j)g[i][j] = (g[i][j]-g[i][j-1])%mod;
    }
    int ans = 0;
    for(int i = 0;i<=len;++i)ans = (ans + 1ll*(g[0][i]+mod)*a[i])%mod;
    ans = 1ll*ans*qpow(C(n+m-2,n-1),mod-2)%mod;
    cout<<ans<<endl;
}