HNOI 2015 실험 비교

제목 링크

제목의 대의.

몇몇 숫자의 크기 관계를 정합니다. >, n≤100 n\le 100 n≤100이 있습니다.

문제풀이

우선 등호는 직접적으로 축소할 수 있고 <=어떤 숫자의 제한이 가장 많게는 하나밖에 없기 때문에 우리는 어릴 때부터 큰 연변으로 여러 그루의 기환수와 나무를 형성한다.분명히 그림에 고리가 있으면 풀이가 없기 때문에 나무만 남는다.처리하기 편리하도록, 우리는 새 점 0을 만들어서, 모든 나무의 뿌리에 연결한다.다음은 분명히 트리 dp이다. 서열에 같은 상황이 존재할 수 있음을 감안하여 f[i][j]f[i][j]f[i][j]는 dp에서 점ii, iii 서브트리가 형성한 서열에서 서로 다른 숫자의 개수를 jjj로 표시한다.우리는 어떻게 두 그루의 나무를 합병할 것인가를 고려한다.마찬가지로 우리는 같은 숫자를 하나의 점으로 간주하면 하나의 서열을 합성한 후에 두 개의 등호가 서로 인접해서 나타날 수 없다.그러면 몇 쌍의 대등한 숫자가 형성되고 각 쌍의 두 숫자는 각각 두 그루의 나무에서 나온다.나머지 숫자는 조합수로 계산하면 된다.우리는 h[i][j]h[i][j]h[i][j]가 길이가 ii임을 나타내는 서열에 jjj의 서로 인접하지 않는 등호를 그리는 방안수를 필요로 한다. 분명히 h[i][j]=h[i-1][j]+h[i-2][j][j][j][j][j]=h[i-1][j]+h[j]+h[j][j][j]h[j][j][j]][j][j]][j2]][j+h1]][h1]이 필요하다.그래서 dp를 할 수 있다. 복잡도 O(n3)O(n^3)O(n3).

#include 
namespace IOStream {
	const int MAXR = 10000000;
	char _READ_[MAXR], _PRINT_[MAXR];
	int _READ_POS_, _PRINT_POS_, _READ_LEN_;
	inline char readc() {
	#ifndef ONLINE_JUDGE
		return getchar();
	#endif
		if (!_READ_POS_) _READ_LEN_ = fread(_READ_, 1, MAXR, stdin);
		char c = _READ_[_READ_POS_++];
		if (_READ_POS_ == MAXR) _READ_POS_ = 0;
		if (_READ_POS_ > _READ_LEN_) return 0;
		return c;
	}
	template<typename T> inline void read(T &x) {
		x = 0; register int flag = 1, c;
		while (((c = readc()) < '0' || c > '9') && c != '-');
		if (c == '-') flag = -1; else x = c - '0';
		while ((c = readc()) >= '0' && c <= '9') x = x * 10 - '0' + c;
		x *= flag;
	}
	template<typename T1, typename ...T2> inline void read(T1 &a, T2&... x) {
		read(a), read(x...);
	}
	inline int reads(char *s) {
		register int len = 0, c;
		while (isspace(c = readc()) || !c);
		s[len++] = c;
		while (!isspace(c = readc()) && c) s[len++] = c;
		s[len] = 0;
		return len;
	}
	inline void ioflush() { fwrite(_PRINT_, 1, _PRINT_POS_, stdout), _PRINT_POS_ = 0; fflush(stdout); }
	inline void printc(char c) {
		if (!c) return;
		_PRINT_[_PRINT_POS_++] = c;
		if (_PRINT_POS_ == MAXR) ioflush();
	}
	inline void prints(const char *s, char c) {
		for (int i = 0; s[i]; i++) printc(s[i]);
		printc(c);
	}
	template<typename T> inline void print(T x, char c = '
') {
		if (x < 0) printc('-'), x = -x;
		if (x) {
			static char sta[20];
			register int tp = 0;
			for (; x; x /= 10) sta[tp++] = x % 10 + '0';
			while (tp > 0) printc(sta[--tp]);
		} else printc('0');
		printc(c);
	}
	template<typename T1, typename ...T2> inline void print(T1 x, T2... y) {
		print(x, ' '), print(y...);
	}
}
using namespace IOStream;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 105, MOD = 1000000007;
struct Edge { int to, next; } edge[MAXN];
int head[MAXN], deg[MAXN], par[MAXN], n, m, tot;
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
inline void addedge(int u, int v) {
	edge[++tot] = (Edge) { v, head[u] };
	head[u] = tot;
}
int mp[MAXN][MAXN], fr[MAXN], to[MAXN], sz[MAXN], que[MAXN];
ll f[MAXN][MAXN], g[MAXN][MAXN], C[MAXN][MAXN], h[MAXN][MAXN];
void dfs(int u) {
	f[u][0] = 1;
	for (int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		dfs(v);
		for (int j = 0; j <= sz[u]; j++)
		for (int k = 1; k <= sz[v]; k++)
		for (int l = 0; l <= j && l <= k; l++)
			(g[u][j + k - l] += h[j + k][l] % MOD * C[j + k - l - l][j - l] % MOD * f[u][j] % MOD * f[v][k]) %= MOD;
		sz[u] += sz[v];
		for (int j = 0; j <= sz[u]; j++)
			f[u][j] = g[u][j], g[u][j] = 0;
	}
	for (int j = ++sz[u]; j > 0; j--) f[u][j] = f[u][j - 1];
	f[u][0] = 0;
}
int main() {
	read(n, m);
	for (int i = 1; i <= n; i++) par[i] = i;
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		int a, b; char o[5];
		read(a), reads(o), read(b);
		if (o[0] == ') ++cnt, fr[cnt] = a, to[cnt] = b;
		else par[find(a)] = find(b);
	}
	for (int i = 1; i <= cnt; i++) {
		int x = find(fr[i]), y = find(to[i]);
		if (x != y && !mp[x][y]) mp[x][y] = 1, addedge(x, y), ++deg[y];
	}
	int he = 0, ta = cnt = 0;
	for (int i = 1; i <= n; i++) if (par[i] == i) {
		if (!deg[i]) addedge(0, i), que[ta++] = i;
		++cnt;
	}
	while (he < ta) {
		int u = que[he++];
		for (int i = head[u]; i; i = edge[i].next) {
			int v = edge[i].to;
			if (!(--deg[v])) que[ta++] = v;
		}
	}
	if (ta != cnt) return puts("0") * 0;
	h[0][0] = C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
	for (int i = 1; i <= n; i++)
	for (int j = 0; j * 2 <= i; j++) {
		h[i][j] = h[i - 1][j];
		if (i > 1 && j > 0) h[i][j] = (h[i][j] + h[i - 2][j - 1]) % MOD;
	}
	dfs(0);
	ll res = 0;
	for (int i = 1; i <= n + 1; i++) res += f[0][i];
	printf("%lld
", res % MOD);
	return 0;
}