_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

BZOJ1494 [NOI2007] 生成树计数

Description

有一个 nn 个点的图。nn 个点排成一排,两个点之间有边当且仅当它们距离不超过 kk (即它们之间隔了不超过 k1k-1 个点)。

求这个图的生成树个数。

n1015,k5n\leqslant10^{15}, k\leqslant5

Solution

题面上的矩阵树定理看上去很吸引人…然而你总不会想拿那个算吧…

可以发现如果有一棵生成树,只取出前 tt 个点之后,它会变成至多 kk 棵树所组成的森林,且每棵树都至少有一个点在最后 kk 个里面(因为如果某棵树的所有点都不在最后 kk 个里面的话,后面的点再也没法和它们连接)。

那么我们可以考虑以后 kk 个点的连通性作为状态进行 DP 。

形式化的,我们把所有 wkw_k (贝尔数)种 kk 个点的连通性标号以 0wk10\dots w_k-1 ,令 fi,j(ik)f_{i,j} (i \geq k) 表示前 ii 个点连成森林,每棵树都有结点在后 kk 个里面,且后 kk 个点的连通性为 jj (即标号为jj 的集合划分方案)的方案数。

那么由于第 ii 个点只能向 iki1i-k\dots i-1 连边, fif_i 只会依赖于 fi1f_{i-1}

考虑转移。如果第 ll 个状态右面追加一个点并向左连边形成第 jj 种状态的方法有 Al,jA_{l, j} 种,那么转移式即为 fi,j=lAl,jfi1,lf_{i, j}=\sum_l A_{l,j}f_{i-1, l}AA 可以通过枚举 ll2k2^k 种连边方式求出(注意判断不合法的情况)。

考虑边界条件。显然 k>nk>n 的时候没有作用,我们可以假定 knk\leqslant n 。那么所有 fi,j(i<k)f_{i, j} (i<k) 都是没有作用(甚至没有定义)的;我们只需要确定 fk,jf_{k,j} 。由于这是前 kk 个点之间都有边,所以把 jj 这个状态中每个连通块当成完全图求出生成树个数再乘起来即可。

之后显然就可以矩阵快速幂加速了。

时间复杂度(零碎的直接抹去)为 O(wn3logn)O(w_n^3\log n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <algorithm>
#include <cstdio>
#include <cstring>

typedef long long LL;

const int K = 5;
const int WK = 52;
const int mod = 65521;

int k;
LL n, A[WK][WK];

struct State{
int A[K];

State() { std::fill(A, A + k, 0); }
State(int *A) { std::copy(A, A + k, this->A); }

void toStd() {
static int B[K * 2];
std::fill(B, B + k * 2, -1);
for (int i = 0, j = 0; i < k; ++i)
A[i] = (B[A[i]] == -1 ? B[A[i]] = j++ : B[A[i]]);
}

int getAns() {
toStd();
static bool vis[K];
std::fill(vis, vis + K, false);
int ans = 1;
for (int i = 0; i < k; ++i) if (!vis[i]) {
int t = 0;
for (int j = i; j < k; ++j)
if (A[i] == A[j]) { vis[j] = true; ++t; }
for (int j = 0; j < t - 2; ++j) ans *= t;
}
return ans;
}

int& getId() {
static int id[15625]; // K^K

toStd();
int ans = 0;
for (int i = 0; i < k; ++i)
ans = ans * k + A[i];
return id[ans];
}

int nextState(int _linkK) {
static bool linkK[K];
static int nxtA[K];

for (int i = 0; i < k; ++i)
linkK[i] = ((_linkK >> i) & 1) == 1;

bool link0 = false;
for (int i = 1; i < k; ++i) if (A[i] == 0) link0 = true;
if (!link0 && !linkK[0]) return -1;
for (int i = 0; i < k; ++i) if (linkK[i])
for (int j = i + 1; j < k; ++j) if (linkK[j] && A[i] == A[j])
return -1;

std::copy(A + 1, A + k, nxtA);
nxtA[k - 1] = k;
for (int i = 0; i < k; ++i) if (linkK[i])
for (int j = 1; j < k; ++j) if (A[i] == A[j])
nxtA[j - 1] = k;

State s(nxtA);
return s.getId();
}
}states[WK];
int cnt;

void dfs(int x, int num) {
static int _t[K];
if (x == k) {
(states[cnt] = State(_t)).getId() = cnt;
++cnt;
return;
}
for (_t[x] = 0; _t[x] <= num; ++_t[x])
dfs(x + 1, std::max(num, _t[x] + 1));
}
inline void GenState() { dfs(0, 0); }

LL An[WK][WK];
void Mul(const LL A[WK][WK], const LL B[WK][WK], LL C[WK][WK]) {
static LL _tmp[WK][WK];
for (int i = 0; i < cnt; ++i)
for (int j = 0; j < cnt; ++j)
_tmp[i][j] = 0;
for (int i = 0; i < cnt; ++i)
for (int j = 0; j < cnt; ++j)
for (int k = 0; k < cnt; ++k)
(_tmp[i][k] += A[i][j] * B[j][k]) %= mod;
for (int i = 0; i < cnt; ++i)
for (int j = 0; j < cnt; ++j)
C[i][j] = _tmp[i][j];
}
int main() {
scanf("%d%lld", &k, &n);
if (n < k) k = n;
GenState();
for (int i = 0; i < cnt; ++i)
for (int S = 0; S < (1 << k); ++S) {
int v = states[i].nextState(S);
if (v != -1) ++A[i][v];
}
for (int i = 0; i < cnt; ++i) An[i][i] = 1;
for (n -= k; n > 0; n >>= 1, Mul(A, A, A))
if ((n & 1) == 1) Mul(An, A, An);
LL ans = 0;
for (int i = 0; i < cnt; ++i)
(ans += An[i][0] * states[i].getAns()) %= mod;
printf("%lld\n", ans);
return 0;
}