[20220115杂题选讲]Count the graphs

Posted on | In ,

简单计数。

大意

有多少 $n$ 个点的带点权无向图，使得 $1$ 和 $2$ 的距离为 $k$？

$n\le 100$，对 $10^9+7$ 取模。时限 2s。

link: http://qoj.ac/contest/802/problem/2158

思路

对整个图进行从 $1$ 开始的最短路分层。

设 $f_{i,j,t}$ 为当前到第 $i$ 层，已经用了 $j$ 个点，这一层 $t$ 个点的方案数。

考察第 $i$ 层的可能情况（注意要留着 $2$ 在第 $k$ 层），容易写出以下的转移式：

系数全部预处理，时间复杂度 $\Theta(n^4)$。

代码

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
#include <cstdio>
#include <algorithm>

namespace mirai {

constexpr int MAXN = 105;
constexpr int MAXM = 10005;
long long pow[MAXM], pow2[MAXN][MAXN], c[MAXN][MAXN];
long long dp[MAXN][MAXN][MAXN];
#define f(i, j, k) (dp[i][j][k])

int main(int argc, char** argv) {
  int n, k, MOD;
  std::scanf("%d%d%d", &n, &k, &MOD);
//  std::printf(" %d\n", n);
  if (MOD == 1) {
    std::puts("0");
    return 0;
  }
  
  pow[0] = 1;
  for (int i = 1; i < MAXM; ++i) {
    pow[i] = (pow[i - 1] * 2) % MOD;
  }
  for (int i = 0; i < MAXN; ++i) {
    pow2[i][0] = 1;
    pow2[i][1] = (pow[i] - 1 + MOD) % MOD;
    for (int j = 1; j < MAXN; ++j) {
      pow2[i][j] = pow2[i][j - 1] * pow2[i][1] % MOD;
    }
  }
  c[0][0] = 1;
  for (int i = 1; i < MAXN; ++i) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j <= i / 2; ++j) {
      c[i][j] = c[i][i - j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
    }
  }
  
//  std::printf(" ");
//  for (int i = 0; i < 10; ++i) {
//    std::printf("%d ", pow[i]);
//  }
//  std::printf("\n ");
//  for (int i = 0; i < 10; ++i) {
//    for (int j = 0; j < 10; ++j) {
//      std::printf("%d ", c[i][j]);
//    }
//    std::printf("\n ");
//  }
//  std::printf("\n");
  
  f(0, 1, 1) = 1;
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int t = 1; t < j; ++t) {
        for (int s = 1; s <= j - t; ++s) {
          f(i, j, t) = (f(i, j, t) + pow[c[t][2]] * pow2[s][t] % MOD * c[n - j + t - (i <= k)][t - (i == k)] % MOD * f(i - 1, j - t, s) % MOD) % MOD;
//          std::printf(" %d %d %d, %d: %d (+= %d) (%d * %d * %d * %d)\n", i, j, t, s, f(i, j, t), 
//           pow[c[t][2]] * pow2[s][t] % MOD * c[n - j + t - (i <= k)][t - (i == k)] % MOD * f(i - 1, j - t, s) % MOD,
//           pow[c[t][2]], pow2[s][t], c[n - j + t - (i <= k)][t - (i == k)], f(i - 1, j - t, s));
        }
//          std::printf("%d %d %d : %d\n", i, j, t, f(i, j, t));
      }
    }
  }
  long long res = 0;
  for (int i = k; i < n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int t = 1; t < n; ++t) {
//        if (i == 2 && j == 5 && t == 1) {
//          std::printf("    %d\n", pow[c[n - j][2]]);
//        }
        res = (res + pow[c[n - j][2]] * f(i, j, t)) % MOD;
      }
    }
  }
  std::printf("%lld\n", res);
  
  return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}