Espionage

Mier_Samuelle · 2026-10-20 21:38:40 · 题解

:::info[Statement]{open}

给定 n,m，共有 n 行 m 层节点，每层节点构成完全图，每个节点与上一层和下一层的节点有连边，求从 (1,1) 出发的哈密顿回路个数，对 10^9+7 取模。

1s，n \le 100，m \le 10^9。

:::

逐层考虑。对于第 t 层下方已经形成的一条链，它一定会纵向延伸两条边到第 t 层，这两条边指向的第 t 层中的点的先后顺序确定，可以捆在一起考虑。记第 t 层下方已经形成了 j 条链，那么第 t 层的自由单点共有 n-2j 个，加上被捆在一起的 j 个节点对，一共 n-j 个块。

现在要将这 n-j 个块连成一些链，然后纵向延伸到下一层。且不能留下孤立的自由单点，否则这些单点连不到回路里去。先定义 A(x,y) 为不考虑限制，将 x 条链连成 y 条链的方案数，有 A(x,y)=\frac{x!}{y!} \cdot \binom{x-1}{y-1}。再定义 M(x,y) 为考虑限制，将 x 条链连成 y 条链的方案数，有 M(x,y)=\sum_{i=0}^{\min(n-2y,x)}(-1)^i \cdot \binom{n-2y}{i} \cdot A(n-y-i,x-i)。

然后就可以 dp 了。定义 F(t,i) 为走到第 t 层，共形成了 i 条链的方案数。转移有 F(t,i)=\sum_{j=0}^{\lfloor n/2\rfloor} M(j,i) \cdot F(t-1,j)。显然可以矩阵优化，可做到 O(n^3 \log m)。这样我们便得到了第 m 层的状态。最后要把第 m 层的链连成一个环，可得答案为 \sum_{i=0}^{\lfloor n/2\rfloor} F(m,i) \cdot (n-i-1)!。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 310;
ll fac[MAXN], inv[MAXN], n, m, d;
struct Matrix{
    int x, y;
    ll a[MAXN][MAXN];
    Matrix operator * (const Matrix &b) const{
        Matrix tmp = {};
        tmp.x = x;
        tmp.y = b.y;
        for (int i = 1; i <= x; i++){
            for (int j = 1; j <= b.y; j++){
                for (int k = 1; k <= b.x; k++){
                    tmp.a[i][j] = (tmp.a[i][j] + b.a[k][j] * a[i][k] % MOD) % MOD;
                }
            }
        }
        return tmp;
    }
}st, base;
Matrix qpow(Matrix x, ll y){
    Matrix res = x;
    y--;
    while (y){
        if (y & 1){
            res = res * x;
        }
        x = x * x;
        y >>= 1;
    }
    return res;
}
ll qpow(ll x, ll y){
    ll res = 1;
    while (y){
        if (y & 1){
            res = res * x % MOD;
        }
        x = x * x % MOD;
        y >>= 1;
    }
    return res;
}
ll cb(ll x, ll y){
    if (x < y){
        return 0;
    }
    return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
ll A(ll x, ll y){
    if (x == 0 && y == 0){
        return 1;
    }
    if (y == 0){
        return 0;
    }
    return fac[x] * inv[y] % MOD * cb(x - 1, y - 1) % MOD;
}
ll M(ll x, ll y){
    ll res = 0;
    for (int i = 0; i <= min(n - 2 * y, x); i++){
        res = (res + ((i & 1 ? -1 : 1) * cb(n - 2 * y, i) % MOD + MOD) % MOD * A(n - y - i, x - i) % MOD) % MOD;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    d = n / 2;
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = qpow(fac[i], MOD - 2);
    }
    base.x = base.y = d + 1;
    for (int i = 1; i <= d + 1; i++){
        for (int j = 1; j <= d + 1; j++){
            base.a[i][j] = M(j - 1, i - 1);
        }
    }
    st.x = 1;
    st.y = d + 1;
    st.a[1][1] = 1;
    Matrix res = st * qpow(base, m - 1);
    ll ans = 0;
    for (int i = 1; i <= d + 1; i++){
        ans = (ans + res.a[1][i] * fac[n - i] % MOD) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

:::