QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480662#7618. Pattern Searchucup-team052#Compile Error//C++142.5kb2024-07-16 17:12:412024-07-16 17:12:43

Judging History

你现在查看的是最新测评结果

  • [2024-07-16 17:12:43]
  • 评测
  • [2024-07-16 17:12:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int md = 1e9 + 7;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

const int N = 1 << 19;

vector <int> adj[N];
int level[N], f[N][18], g[N][18], emp[N];
int n;

bool cmp(int i, int j) {
	return level[i] < level[j];
}

int dp[N], ndp[N];
void dfs1(int u, int fa) {
	vector <int> son;
	for (auto v : adj[u]) {
		if (v == fa) continue;
		dfs1(v, u);
		son.push_back(v);
	}
	sort(son.begin(), son.end(), cmp);
	auto gen_dp = [&]() {
		int nowlevel = 0;
		dp[0] = 1;
		for (auto v : son) {
			memset(ndp, 0, (1 << (level[v] + 1)) * 4);
			for (int i = 0; i < (1 << (nowlevel + 1)); i++) {
				if (!dp[i]) continue;
				ndp[i] = add(ndp[i], mul(dp[i], emp[v]));
				for (int j = 0; j <= level[v]; j++) {
					if ((i >> j) & 1) continue;
					ndp[i | (1 << j)] = add(ndp[i | (1 << j)], mul(dp[i], f[v][j]));
				}
			}
			memcpy(dp, ndp, (1 << (level[v] + 1)) * 4);
			nowlevel = level[v];
		}
	};
	int mxl = 0;
	if (son.size()) mxl = level[son.back()] + 1;
	// calc f
	for (int i = 0; i <= mxl; i++) {
		f[u][i] = dp[(1 << i) - 1];
		if (f[u][i]) level[u] = i;
	}
	// calc g
	for (int i = 0; i <= min(17, mxl); i++) {
		if (i != mxl) {
			for (int j = i; j <= mxl - 1; j++) {
				g[u][i] = add(g[u][i], dp[(1 << (j + 1)) - 1 - (1 << i)]);
			}
		} else {
			g[u][i] = dp[(1 << mxl) - 1];
		}
	}
	for (auto v : son[u]) {
		// g[v][0], g[v][1], ..., g[v][level[v]]
		assert(emp[v]); // fake solution
		int inv = fpow(emp[v], md - 2);
		memset(ndp, 0, (1 << level[v]) * 4);
		for (int i = 0; i < (1 << level[v]); i++) {
			ndp[i] = dp[i];
			for (int j = 0; j < level[v]; j++) {
				if ((i >> j) & 1) {
					ndp[i] = sub(ndp[i], mul(ndp[i ^ (1 << j)], f[v][j]));
				}
			}
			ndp[i] = mul(ndp[i], inv);
		}
		// calc emp
		for (int i = 0; i <= level[v]; i++) {
			emp[u] = add(emp[u], ndp[]);
		}
	}
	for (int i = 0; i <= level[u]; i++) {
		emp[i] = add(emp[i], f[u][i]);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs1(1, 0);
	printf("%d\n", emp[1]);
	return 0;
}

Details

answer.code: In function ‘void dfs1(int, int)’:
answer.code:82:28: error: ‘begin’ was not declared in this scope; did you mean ‘std::begin’?
   82 |         for (auto v : son[u]) {
      |                            ^
      |                            std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166,
                 from answer.code:1:
/usr/include/c++/13/valarray:1232:5: note: ‘std::begin’ declared here
 1232 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
answer.code:82:28: error: ‘end’ was not declared in this scope; did you mean ‘std::end’?
   82 |         for (auto v : son[u]) {
      |                            ^
      |                            std::end
/usr/include/c++/13/valarray:1259:5: note: ‘std::end’ declared here
 1259 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
answer.code:98:50: error: expected primary-expression before ‘]’ token
   98 |                         emp[u] = add(emp[u], ndp[]);
      |                                                  ^
answer.code: In function ‘int main()’:
answer.code:107:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:110:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~