题解 P2109 【[NOI2007]生成树计数】

· · 题解

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

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

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 的贡献算上.

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

#### Part 4 Code ```cpp #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; } ```