思路

考虑用动态规划解决这个问题。

令 为有 个座位最后坐下的期望人数。

当有 个座位时，第 个人有 种选择，可以选择第 个座位坐下。

当第 个人在第 个座位坐下后，第 个人的左边就有 个座位可以坐，对应的期望人数可以表示为 ，右边有 个座位可以坐，对应的期望人数为 ，因此，第 个人坐在第 个座位的情况下，最后坐下的期望人数为 。

因为第 个人是在 个座位随机选择一个坐下，所以第 个人坐到第 个座位的概率为 。

因为第 个座位有从 到 共 种情况，所以最后坐下的期望人数为 。

因为 ，所以 ，且 ，显然，当座位数量不为正数时，坐下人数必然为 ，所以有效范围实则为 ， 则可以变式为 。

令 ，。

复杂度

时间复杂度和空间复杂度均为

代码实现

// Problem: biubiubiu坐地铁
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/25193
// Memory Limit: 2 MB
// Time Limit: 25193000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5, mod = 1e9 + 7;

int qmi(int a, int b)
{
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int inv(int x)
{
    return qmi(x, mod - 2);
}

int n;
int f[N], g[N];

void solve()
{
    cin >> n;
    f[1] = f[2] = 1;
    for (int i = 1; i <= n; i++) {
        if (i > 2)
            f[i] = (i + 2 * g[i - 2]) % mod * inv(i) % mod;
        g[i] = (g[i - 1] + f[i]) % mod;
    }
    cout << f[n];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}