自动搬运

查看原文

来自洛谷，原作者为

	Kinandra :D

搬运于2025-08-24 21:34:06，当前版本为作者最后更新于2020-05-08 08:31:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

标签: 矩阵树定理, 高斯消元, 矩阵快速幂.

(就我一个老实人真的按照题目讲的矩阵树定理做的吗?

Part 1 观察矩阵

为了方便讨论, 令 $k=3$ , 其余情况可以很容易的推广.

我们考虑 $n=9$ 时的基尔霍夫矩阵(为了方便观察懒得打,值为 $0$ 的位置用空表示):

$$\left[ \begin {matrix} 3&-1&-1&-1&&&&&\\ -1&4&-1&-1&-1&&&&\\ -1&-1&5&-1&-1&-1&&&\\ -1&-1&-1&6&-1&-1&-1&&\\ &-1&-1&-1&6&-1&-1&-1&\\ &&-1&-1&-1&6&-1&-1&-1\\ &&&-1&-1&-1&5&-1&-1\\ &&&&-1&-1&-1&4&-1\\ &&&&&-1&-1&-1&3 \end {matrix} \right] $$

惊讶(并不)地发现矩阵的 $k+1\sim n-k$ 行都是由 $k$ 个 $-1$ , 一个 $2k$ 和 $k$ 个 $-1$ 拼接而成的.

求行列式通常需要将矩阵消成上三角的形式, 并将对角线上的元素相乘, 我们通过若干次交换两行将矩阵变成如下形式:

$$\left[ \begin {matrix} -1&-1&-1&6&-1&-1&-1&&\\ &-1&-1&-1&6&-1&-1&-1&\\ 3&-1&-1&-1&&&&&\\ -1&4&-1&-1&-1&&&&\\ -1&-1&5&-1&-1&-1&&&\\ &&-1&-1&-1&6&-1&-1&-1\\ &&&-1&-1&-1&5&-1&-1\\ &&&&-1&-1&-1&4&-1\\ &&&&&-1&-1&-1&3 \end {matrix} \right] $$

这里矩阵有点小, 可能看不出这么交换的目的, 考虑一个 $n$ 较大的情况( $n=17$ ):

$$\left[ \begin {matrix} -1&-1&-1&6&-1&-1&-1&&\\ &-1&-1&-1&6&-1&-1&-1&\\ &&-1&-1&-1&6&-1&-1&-1&\\ &&&-1&-1&-1&6&-1&-1&-1&\\ &&&&-1&-1&-1&6&-1&-1&-1&\\ &&&&&-1&-1&-1&6&-1&-1&-1&\\ &&&&&&-1&-1&-1&6&-1&-1&-1&\\ &&&&&&&-1&-1&-1&6&-1&-1&-1&\\ &&&&&&&&-1&-1&-1&6&-1&-1&-1&\\ &&&&&&&&&-1&-1&-1&6&-1&-1&-1&\\ 3&-1&-1&-1&&&&&\\ -1&4&-1&-1&-1&&&&\\ -1&-1&5&-1&-1&-1&&&\\ &&&&&&&&&&-1&-1&-1&6&-1&-1&-1\\ &&&&&&&&&&&-1&-1&-1&5&-1&-1\\ &&&&&&&&&&&&-1&-1&-1&4&-1\\ &&&&&&&&&&&&&-1&-1&-1&3 \end {matrix} \right] $$

我们发现矩阵的前 $n-2k-1$ 行已经形成了一个 '天然' 的上三角, 并且这 $n-2k-1$ 行的形式都十分相似: $k$ 个 $-1$ , $1$ 个 $2k$ 和 $k$ 个$-1$ 一次拼接而成.

Part 2 高斯消元

我们考虑将矩阵的用前 $n-2k-1$ 行去消元第 $n-2k\sim n-k-1$ 行过程. 由于前 $n-2k-1$ 行非 $0$ 位置个数都为 $2k+1$ 且非 $0$ 的位置具有特殊性, 所以消元的过程中被消的行向量非 $0$ 位置数量始终不大于 $2k$ (但是每消一次整体向右移动一个位置), 考虑一次消元这 $2k$ 个的值是如何变化的: 我们有这样一个行向量

$$\left[ \begin {matrix} a_0&a_1&a_2&a_3&a_4&a_5&0 \end {matrix} \right] $$

为了消去 $a0$ , 加上如下行向量:

$$a_0\left[ \begin {matrix} -1&-1&-1&6&-1&-1&-1 \end {matrix} \right] $$

从而得到:

$$\left[ \begin {matrix} 0&a_1-a_0&a_2-a_0&a_3+6a_0&a_4-a_0&a_5-a_0&-a_0 \end {matrix} \right] $$

记为:

$$\left[ \begin {matrix} 0&a'_0&a'_1&a'_2&a'_3&a'_4&a'_5 \end {matrix} \right] $$

显然这个消元可以通过矩阵来转移:

$$\left[ \begin {matrix} a'_0&a'_1&a'_2&a'_3&a'_4&a'_5 \end {matrix} \right]= \left[ \begin {matrix} a_0&a_1&a_2&a_3&a_4&a_5 \end {matrix} \right] \left[ \begin {matrix} -1&1&0&0&0&0\\ -1&0&1&0&0&0\\ 6&0&0&1&0&0\\ -1&0&0&0&1&0\\ -1&0&0&0&0&1\\ -1&0&0&0&0&0 \end {matrix} \right] $$

于是我们就可以通过快速幂来加速高斯消元. 我们需要消 $k$ 行, 所以这个部分的时间复杂度为 $\mathcal O(k^4\log n)$ .

将第 $n-2k\sim n-k-1$ 行用前 $n-2k-1$ 行消元过后, 非 $0$ 位置都分布在 $n-k\sim n$ 行, 我们暴力对剩余部分($n-2k\sim n-1$ 行)消元即可, 这个部分时间复杂度为 $\mathcal O(k^3)$.

总时间复杂度 $\mathcal O(k^4\log n)$.

Part 3 细节

Part 1 中我们进行了若干次交换两行的操作, 这会使行列式乘上若干个 $-1$ , 不要忘记计算.

最后算行列式时不要忘记将 '天然' 的上三角中的 $-1$ 的贡献算上.

注意要计算的是主余子式, 不要忘记去掉一行一列.

$n\leqslant 2k$ 时不存在'天然'的上三角, 但是此时直接暴力消元是 $\mathcal O(k^3)$ , 特殊处理即可.

Part 4 Code

#include <bits/stdc++.h>
#define mod 65521
using namespace std;
long long read();
int M(int x) { return x >= mod ? x - mod : x; }
void Add(int& x, int y) { (x += y) >= mod ? x -= mod : x; }
int fsp(unsigned bs, int p) {
    int rt = 1;
    while (p) {
        if (p & 1) rt = bs * rt % mod;
        bs = bs * bs % mod, p >>= 1;
    }
    return rt;
}

long long n;
int k, lim;

int b[102][102];
void work1() {
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= min(i + k, (int)n); ++j)
            ++b[i][i], ++b[j][j], b[i][j] = b[j][i] = mod - 1;
    lim = n - 1;
}

int K;
struct Mat {
    int a[21][21];
    int* operator[](int p) { return a[p]; }
    Mat operator*(Mat& b) {
        static Mat rt;
        for (int i = 1; i <= K; ++i)
            for (int j = 1; j <= K; ++j) {
                rt[i][j] = 0;
                for (int k = 1; k <= K; ++k)
                    Add(rt[i][j], 1ll * a[i][k] * b[k][j] % mod);
            }
        return rt;
    }
} bs, res;

int c[21];

void work2() {
    K = k << 1;
    for (int i = 1; i <= K; ++i)
        bs[i][1] = mod - 1, bs[i][i + 1] = res[i][i] = 1;
    bs[k][1] = K;
    for (long long p = n - K - 1; p; p >>= 1)
        (p & 1) ? res = res * bs : res, bs = bs * bs;

    for (int i = 1; i <= k; ++i) {
        memset(c, 0, sizeof c);
        for (int j = 1; j <= i + k; ++j) c[j] = mod - 1;
        c[i] = k + i - 1;
        for (int j = 1; j <= K; ++j)
            for (int k = 1; k <= K; ++k)
                Add(b[i][j], 1ll * res[j][k] * c[k] % mod);
    }

    for (int i = k + 1; i <= K; ++i) {
        for (int j = i - k; j <= K; ++j) b[i][j] = mod - 1;
        b[i][i] = 3 * k - i + 1;
    }

    lim = K;
    if (1ll * (n - K - 1) * (k + 1) & 1)
        for (int i = 1; i <= K; ++i) b[1][i] = mod - b[1][i];
}

void solve() {
    int res = 1, ny;
    for (int i = 1; i <= lim; ++i) {
        if (!b[i][i])
            for (int j = i; j <= lim; ++j)
                if (b[j][i]) {
                    swap(b[i], b[j]), res = mod - res;
                    break;
                }
        res = 1ll * res * b[i][i] % mod, ny = fsp(b[i][i], mod - 2);
        for (int j = i; j <= lim; ++j) b[i][j] = 1ll * b[i][j] * ny % mod;
        for (int j = i + 1; j <= lim; ++j)
            for (int k = lim; k >= i; --k)
                Add(b[j][k], mod - 1ll * b[j][i] * b[i][k] % mod);
    }
    printf("%d\n", M(res));
}
int main() {
    k = read(), (n = read()) <= 20 ? work1() : work2(), solve();
    return 0;
}

long long read() {
    long long x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}