思路与算法

每次离家直到首次回家称一个段。长度2j的段必须全部在同一侧，去掉首末步后与合法括号串一一对应，有2C(j-1)种。令N=n/2,M=m/2，得到f[N]=Σ(1≤j≤M)2C(j-1)f[N-j]，f[0]=1。把x^N在特征多项式x^M-Σa[j]x^(M-j)下快速幂取余，再与前M项点积，求出大下标。

正确性说明

每条最终回家的散步按首次回家时刻唯一分段，每段长度≤m是原离家时间限制。首返段去边界后为正侧或负侧Dyck路径，给Catalan计数，乘法与分类求和得卷积递推。特征关系把x^M替换成低次项，恰与序列递推同构，故多项式快速幂的线性组合等于目标项。

复杂度

Catalan和初值初始化O(M²+MlogMOD)，多项式乘法及约简O(M²)，快速幂O(M²logN)，空间O(M)，包含临时卷积2M-1数组。M≤50。

易错点

n,m均为偶数。M=1时x模特征关系是常数2，程序单独设基。不要把任意回家段误当首返段，否则重复计数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long pw(long long a, long long n) {
    long long r = 1;
    while (n) {
        if (n & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    int m;
    cin >> n >> m;
    n /= 2;
    m /= 2;
    vector<long long> a(m + 1), cat(m), init(m);
    cat[0] = 1;
    for (int i = 1; i < m; i++)
        cat[i] = cat[i - 1] * (4 * i - 2) % MOD * pw(i + 1, MOD - 2) % MOD;
    for (int i = 1; i <= m; i++)
        a[i] = 2 * cat[i - 1] % MOD;
    init[0] = 1;
    for (int i = 1; i < m; i++)
        for (int j = 1; j <= i; j++)
            init[i] = (init[i] + a[j] * init[i - j]) % MOD;
    auto mul = [&](vector<long long> x, vector<long long> y) {
        vector<long long> z(2 * m - 1);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                z[i + j] = (z[i + j] + x[i] * y[j]) % MOD;
        for (int i = 2 * m - 2; i >= m; i--)
            for (int j = 1; j <= m; j++)
                z[i - j] = (z[i - j] + z[i] * a[j]) % MOD;
        z.resize(m);
        return z;
    };
    vector<long long> r(m), b(m);
    r[0] = 1;
    if (m == 1)
        b[0] = a[1];
    else
        b[1] = 1;
    while (n) {
        if (n & 1)
            r = mul(r, b);
        b = mul(b, b);
        n >>= 1;
    }
    long long ans = 0;
    for (int i = 0; i < m; i++)
        ans = (ans + r[i] * init[i]) % MOD;
    cout << ans << '\n';
}