HNOI 2015 실험 비교

49253 단어 dp
제목 링크

제목의 대의.


몇몇 숫자의 크기 관계를 정합니다. >, 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; }

좋은 웹페이지 즐겨찾기