水题笔记_ [中山市选2010]生成树 [Matrix树定理(划掉)]

又是一道思博好题啊

懵逼的 题目

qwq

扯淡的 题解

显然可以矩阵树定理做出来

我和昊哥的 低端做法

给定的图有$5n$条边, $4n$个点, 所以一共要删掉$n + 1$条边, 而且中间的环是一定要删除一些边的…
$$
ans = \sum^n_{i = 1}{\mathrm C ^i_n \cdot 4i \cdot4^{n - i}}
$$
考虑删除中间环上的$i$条边, 确定删除环上的哪些边就有$\mathrm C_n^i$种方案; 在这些删除边的$i$个五边形中, 一共只能也必须删掉一条边(要不然就不联通了), 这就有$4i$种选择; 在其他的没有删除过边的$n - i$个五边形中, 每个五边形都要删除一条边, 一共是$n ^{n - i}$种选择; 根据乘法原理, 删掉$i$条边时对答案的贡献就是$\mathrm C_n^i \cdot 4i \cdot4^{n - i}$

popoqqq大爷的 高端做法

我们发现, 在$n$个五边形中, 有一个要删掉$2$条边(且必须有一条边在中间的环上), 有$n - 1$个要删掉$1$条边, 然后就可以得出
$$
ans = 4 \cdot n \cdot 5 ^{n - 1}
$$

沙茶的 代码

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
/**************************************************************
Problem: 2467
User: Cansult
Language: C++
Result: Accepted
Time:20 ms
Memory:1376 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define aufun 2007
#define int long long
#define MAXN (100 + 5)
using namespace std;
int c[MAXN][MAXN];
int power(int x, int y) // return x ^ y;
{
int re = 1;
for (int i = 1; i <= y; i++)
re = re * x % aufun;
return re;
}
void init()
{
c[1][0] = c[1][1] = 1;
for (int i = 2; i < MAXN; i++)
{
c[i][0] = 1;
for (int j = 1; j <= i; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % aufun;
}
}
main()
{
init();
int t;
scanf("%lld", &t);
while (t--)
{
int n;
scanf("%lld", &n);
int x = 0;
for (int i = 1; i <= n; i++)
x = (x + ((c[n][i] * (i * 4)) % aufun) * power(4, n - i)) % aufun;
printf("%lld\n", x);
}
return 0;
}

By 昊哥的$3001$号小弟 Cansult