简单变相

最优题解

可以发现，每次牛牛所在格子的列数必定+1，则在当前格子的方案数只与上一格3个格子的方案数有关。
所以用表示从(1,1)到(i,j)的方案数，如果(i,j)有障碍物那么方案数就是0，否则等于走一步能到达它的格子的方案数的累加。
因为是按列推进的，所以为了cache友好，把第一维作为列，第二维作为行
时间和空间复杂度都是

int dp[100005][3];//dp(i,j)表示从(1,1)到(j+1,i)的方案数。
int vis[100005][3];
int solve(int n, int m, vector<int> &x, vector<int> &y){
    assert(x.size() == m && y.size() == m);
    memset(dp, 0, sizeof dp); memset(vis, 0, sizeof vis);
    for(int i = 0; i < m; ++i) vis[y[i]][x[i]-1] = 1;
    dp[1][0] = 1; int mod = 1e9 + 7;
    for(int i = 2; i <= n; ++i){
        if(!vis[i][0]) dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod;
        else dp[i][0] = 0;
        if(!vis[i][1]) dp[i][1] = ((dp[i-1][0] + dp[i-1][1])%mod + dp[i-1][2])%mod;
        else dp[i][1] = 0;
        if(!vis[i][2]) dp[i][2] = (dp[i-1][1] + dp[i-1][2])%mod;
        else dp[i][2] = 0;
    }
    assert(dp[n][2] < mod && dp[n][2] >= 0);
    return dp[n][2];
}