又是一道思博好题啊

懵逼的 题目

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}
$$

沙茶的 代码

/**************************************************************
    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