Submission #660027

#	Time	Username	Problem	Language	Result	Execution time	Memory
660027		highway_to_hell	Star Trek (CEOI20_startrek)	C++14	50 / 100	1095 ms	80336 KiB

startrek

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	if (a < 0) a += mod;
	return a;
}
int mul(int a, int b) {
	return 1ll*a*b%mod;
}
int pw(int a, ll b) {
	int out = 1;
	while (b) {
		if (b&1) out = mul(out, a);
		a = mul(a,a);
		b>>=1;
	}
	return out;
}

const int N = 1e5 + 50, LG = 60;
int n;
ll d;
vector<int> adj[N];
pii dpdw[N], dpup[N], dp[LG][N][2], out[N][2], tmp[N][2]; 

void dfs(int u, int p) {
	int cnt, sum, sbd;
	cnt = sum = sbd = 0;
	for (int v:adj[u]) {
		if(v == p) continue;
		dfs(v, u);
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	dpdw[u].F = !cnt;
	if (cnt >= 2) return;
	dpdw[u].S = (cnt? sbd:sum+1);
}

void sfd(int u, int p) {
	int cnt, sum, sbd;
	cnt = dpup[u].F;
	sum = dpup[u].S;
	sbd = dpup[u].F*dpup[u].S;
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;
	}
	for (int v:adj[u]) {
		if (v == p) continue;
		sum = add(sum, -dpdw[v].S);
		sbd = add(sbd, -dpdw[v].F*dpdw[v].S);
		cnt -= dpdw[v].F;
		
		dpup[v].F = !cnt;
		if (cnt < 2) dpup[v].S = (cnt? sbd:sum+1);

		sum = add(sum, dpdw[v].S);
		sbd = add(sbd, dpdw[v].F*dpdw[v].S);
		cnt += dpdw[v].F;

		sfd(v, u);
	}
}

void solve() {
	cin >> n >> d;
	for (int i = 1; i <= n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	sfd(1, 0);
	for (int u = 1; u <= n; u++) {
		if (dpdw[u].F) {
			dp[0][u][dpup[u].F^1] = {1, (dpup[u].F? dpup[u].S : add(dpdw[u].S, dpup[u].S))};
		}
		else {
			dp[0][u][0] = {1, (dpup[u].F ? 0 : dpdw[u].S)};
		}
	}
	for (int k = 1; k < LG; k++) {
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k-1][u][1].F);
			sa = add(sa, dp[k-1][u][0].S);
			sb = add(sb, dp[k-1][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][0].F, pw(mul(n, n), 1ll<<(k-1))));
			dp[k][u][0].F = add(dp[k][u][0].F, -mul(dp[k-1][u][0].S, sum));
			dp[k][u][0].F = add(dp[k][u][0].F, mul(dp[k-1][u][1].S, sum));
			dp[k][u][0].S = add(mul(dp[k-1][u][0].S, sa), mul(dp[k-1][u][1].S, sb));

			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][1].F, pw(mul(n, n), 1ll<<(k-1))));
			dp[k][u][1].F = add(dp[k][u][1].F, -mul(dp[k-1][u][1].S, sum));
			dp[k][u][1].F = add(dp[k][u][1].F, mul(dp[k-1][u][0].S, sum));
			dp[k][u][1].S = add(mul(dp[k-1][u][1].S, sa), mul(dp[k-1][u][0].S, sb));
		}
	}

	bool flg = 0;
	d++;
	for (int k = 0; k < LG; k++) {
		if (!(d>>k&1)) continue;
		if (!flg) {
			for (int u = 1; u <= n; u++) {
				out[u][0] = dp[k][u][0];
				out[u][1] = dp[k][u][1];
			}
			flg = 1;
			continue;
		}
		int sum = 0;
		int sa = 0, sb = 0;
		for (int u = 1; u <= n; u++) {
			sum = add(sum, dp[k][u][1].F);
			sa = add(sa, dp[k][u][0].S);
			sb = add(sb, dp[k][u][1].S);
		}
		for (int u = 1; u <= n; u++) {
			tmp[u][0] = tmp[u][1] = {0, 0};

			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][0].F, pw(mul(n, n), 1ll<<k)));
			tmp[u][0].F = add(tmp[u][0].F, -mul(out[u][0].S, sum));
			tmp[u][0].F = add(tmp[u][0].F, mul(out[u][1].S, sum));
			tmp[u][0].S = add(mul(out[u][0].S, sa), mul(out[u][1].S, sb));

			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][1].F, pw(mul(n, n), 1ll<<k)));
			tmp[u][1].F = add(tmp[u][1].F, -mul(out[u][1].S, sum));
			tmp[u][1].F = add(tmp[u][1].F, mul(out[u][0].S, sum));
			tmp[u][1].S = add(mul(out[u][1].S, sa), mul(out[u][0].S, sb));

			out[u][0] = tmp[u][0];
			out[u][1] = tmp[u][1];
		}
	}
	cout << out[1][0].F << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15