BZOJ1494 [NOI2007] 生成树计数

2018 年 03 月 21 日发布.

Description

有一个 $n$ 个点的图。$n$ 个点排成一排，两个点之间有边当且仅当它们距离不超过 $k$ （即它们之间隔了不超过 $k-1$ 个点）。

求这个图的生成树个数。

$n\leqslant10^{15}, k\leqslant5$ 。

Solution

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

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

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

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

那么由于第 $i$ 个点只能向 $i-k\dots i-1$ 连边， $f_i$ 只会依赖于 $f_{i-1}$ 。

考虑转移。如果第 $l$ 个状态右面追加一个点并向左连边形成第 $j$ 种状态的方法有 $A_{l, j}$ 种，那么转移式即为 $f_{i, j}=\sum_l A_{l,j}f_{i-1, l}$ 。 $A$ 可以通过枚举 $l$ 及 $2^k$ 种连边方式求出（注意判断不合法的情况）。

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

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

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

Code

#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;
}