【noi2007】生成树计数 连通性DP

有n个点，距离不超过k的有连边，求生成树个数。

用最小表示法和矩阵乘法。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex)
using namespace std;
typedef long long LL;
const int mod = 65521, M = 60000, N = 60;
int m, n, hs[M], tmp, d[8], u[8], b[8], c[8], v[8]; LL l;
struct Matr {
	LL a[N][N];
	Matr() { memset(a, 0, sizeof(a)); }
} p, q;
Matr operator *(Matr X, Matr Y) {
	Matr Z;
	Rep(i, 1, n) {
		Rep(k, 1, n) {
			Rep(j, 1, n) (Z.a[i][j] += X.a[i][k] * Y.a[k][j]) %= mod;
		}
	}
	return Z;
}
int F(int x) { return (x == m) ? d[m] : F(x + 1) * 6 + d[x]; }
int F2(int x) { return (x == m) ? u[m] : F2(x + 1) * 6 + u[x]; }
void Find(int x, int z) {
	if (x == m + 1) {
		tmp = F(1), hs[tmp] = ++ n;
		Rep(i, 1, 5) b[i] = 0;
		Rep(i, 1, m) b[ d[i] ] ++;
		p.a[1][n] = 1;
		Rep(i, 1, z) p.a[1][n] *= v[ b[i] ];
		return ;
	}
	Rep(i, 1, z) d[x] = i, Find(x + 1, z);
	d[x] = z + 1, Find(x + 1, z + 1);
}
void Matc(int x) {
	if (x == m + 1) {
		Rep(i, 1, 6) b[i] = 0; int cz = 0;
		Rep(i, 2, m) {
			if (c[ d[i] ]) {
				if (!b[m + 1]) b[m + 1] = ++ cz;
				u[i - 1] = b[m + 1];
			} else {
				if (!b[ d[i] ]) b[ d[i] ] = ++ cz;
				u[i - 1] = b[ d[i] ];
			}
		}
		u[m] = b[m + 1]; if (!u[m]) u[m] = ++ cz;
		q.a[tmp][ hs[ F2(1) ] ] ++;
		return ;
	}
	Matc(x + 1);
	if (!c[ d[x] ]) c[ d[x] ] = 1, Matc(x + 1), c[ d[x] ] = 0;
}
void Find2(int x, int z, int t) {
	if (x == m + 1) {
		tmp = hs[ F(1) ];
		c[1] = 1, Matc(2);
		if (t) c[1] = 0, Matc(2);
		return ;
	}
	Rep(i, 1, z) d[x] = i, Find2(x + 1, z, t | (i == 1));
	d[x] = z + 1, Find2(x + 1, z + 1, t);
}
void Build() {
	v[1] = v[2] = 1, v[3] = 3, v[4] = 16, v[5] = 125;
	d[1] = 1, Find(2, 1), Find2(2, 1, 0);
}
void Pow() {
	while (l) {
		if (l & 1) p = p * q;
		q = q * q, l >>= 1;
	}
}
int main()
{
	scanf ("%d%lld", &m, &l); l -= m;
	Build(); Pow();
	printf("%lld\n", p.a[1][1]);

	return 0;
}