题目大意：

思路：基尔霍夫矩阵求生成树个数，不会。

可是能够暴力打表。（我才不会说我调试force调试了20分钟。。。

CODE(force.cc)：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAX 1000

using namespace std;

struct Edge{

	int x,y;

	Edge(int _,int __):x(_),y(__) {}

	Edge() {}

}edge[MAX];

int edges;

int status;

int father[MAX];

int Find(int x)

{

	if(father[x] == x)	return x;

	return father[x] = Find(father[x]);

}

inline bool Unite(int x,int y)

{

	int fx = Find(x);

	int fy = Find(y);

	if(fx != fy) {

		father[fx] = fy;

		return true;

	}

	return false;

}

int main()

{

	for(int i = 1; i <= 20; ++i) {

		edges = 0;

		for(int j = 1; j <= i; ++j)

			edge[++edges] = Edge(0,j);

		for(int j = 1; j < i; ++j)

			edge[++edges] = Edge(j,j + 1);

		edge[++edges] = Edge(i,1);

		int ans = 0;

		for(int j = 1; j <= (1 << edges); ++j) {

			int added = 0;

			for(int k = 0; k <= i; ++k)

				father[k] = k;

			for(int k = 0; k < edges; ++k)

				added += (j >> k)&1;

			if(added  != i)	continue;

			added = 0;

			for(int k = 0; k < edges; ++k)

				if((j >> k)&1)

					added += Unite(edge[k + 1].x,edge[k + 1].y);

			ans += (added == i);

		}

		cout << i << ':' << ans << endl;

	}

	return 0;

}

打出的表是这种。。

后面的数太大了爆了。

。

非常明显能够看出奇数的数都是全然平方数。

把它们开跟，然后经过艰苦卓绝的分析之后，得到了一个递推式：

f[i] = f[i - 1] + Σf[j] + 2 (j∈[1,i - 1])，答案是f[n] ^ 2

有了这个结论，偶数的就好办了。能够看到，偶数的除以5之后也是全然平方数，和上面非常像，它的递推式是：

f[i] = f[i - 1] + Σf[j] + 1 (j∈[i,i - 1])，答案是f[n] ^ 2 * 5

至于为什么递推式长这样，谜。

CODE：

#include <cstdio>

#include <iomanip>

#include <cstring>

#include <iostream>

#include <algorithm>

#define BASE 10000

#define MAX 1010

using namespace std;

struct BigInt{

	int num[MAX],len;

	BigInt(int _ = 0) {

		memset(num,0,sizeof(num));

		len = _ ? 1:0;

		num[1] = _;

	}

	BigInt operator +(const BigInt &a)const {

		BigInt re;

		re.len = max(len,a.len);

		int temp = 0;

		for(int i = 1; i <= re.len; ++i) {

			re.num[i] = num[i] + a.num[i] + temp;

			temp = re.num[i] / BASE;

			re.num[i] %= BASE;

		}

		if(temp)	re.num[++re.len] = temp;

		return re;

	}

	BigInt operator *(const BigInt &a)const {

		BigInt re;

		for(int i = 1; i <= len; ++i)

			for(int j = 1; j <= a.len; ++j) {

				re.num[i + j - 1] += num[i] * a.num[j];

				re.num[i + j] += re.num[i + j - 1] / BASE;

				re.num[i + j - 1] %= BASE;

			}

		re.len = len + a.len;

		if(!re.num[re.len])	--re.len;

		return re;

	}

};

ostream &operator <<(ostream &os,const BigInt &a)

{

	os << a.num[a.len];

	for(int i = a.len - 1; i; --i)

		os << fixed << setw(4) << setfill('0') << a.num[i];

	return os;

}

int k;

BigInt f[110],g[110];

int main()

{

	cin >> k;

	if(k&1) {

		k = (k + 1) >> 1;

		f[1] = BigInt(1),f[2] = BigInt(4);

		g[1] = BigInt(1),g[2] = BigInt(5);

		for(int i = 3; i <= k; ++i) {

			f[i] = f[i - 1] + g[i - 1] + BigInt(2);

			g[i] = g[i - 1] + f[i];

		}

		cout << f[k] * f[k] << endl;

	}

	else {

		k >>= 1;

		f[1] = BigInt(1),f[2] = BigInt(3);

		g[1] = BigInt(1),g[2] = BigInt(4);

		for(int i = 3; i <= k; ++i) {

			f[i] = f[i - 1] + g[i - 1] + BigInt(1);

			g[i] = g[i - 1] + f[i];

		}

		cout << f[k] * f[k] * BigInt(5) << endl;

	}

	return 0;

}