Submission #482427

#	Time	Username	Problem	Language	Result	Execution time	Memory
482427		pooyashams	Star Trek (CEOI20_startrek)	C++17	45 / 100	119 ms	64388 KiB

startrek

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;

const int maxn = 2e5+10;
const int mod = 1e9+7;

struct mat
{
	vector<vector<ll>> vals;
	int n, m;
	mat(int _n, int _m, bool I=false)
	{
		n = _n;
		m = _m;
		vals = vector<vector<ll>>(n);
		fill(vals.begin(), vals.end(), vector<ll>(m, 0));
		if(I and n == m)
			for(int i = 0; i < n; i++)
				vals[i][i] = 1;
	}
	inline vector<ll>& operator[](int i)
	{
		return vals[i];
	}
	inline mat operator*(const mat &other)
	{
		assert(m == other.n);
		mat out(n, other.m, false);
		for(int i = 0; i < n; i++)
			for(int k = 0; k < m; k++)
				for(int j = 0; j < other.m; j++)
					out[i][j] = (out[i][j] + vals[i][k] * other.vals[k][j]) % mod;
		return out;
	}
};

inline ll bpow(ll x, ll y)
{
	x = x%mod;
	ll ans = 1;
	while(y > 0)
	{
		if(y & 1)
			ans = ans * x % mod;
		x = x*x % mod;
		y >>= 1;
	}
	return ans;
}

inline mat mpow(mat x, ll y)
{
	mat ans(x.n, x.n, true);
	while(y > 0)
	{
		if(y & 1)
			ans = ans * x;
		x = x*x;
		y >>= 1;
	}
	return ans;
}

inline ll inv(ll x)
{
	return bpow(x, mod-2);
}

vector<int> G[maxn];
vector<int> kids[maxn];
int par[maxn];

bool vis[maxn];
bool wndn[maxn];
bool wnup[maxn];

int crdn[maxn];
int crup[maxn];

bool finwn[maxn];
int fincr[maxn];

void dfs1(int v)
{
	if(vis[v]) return;
	vis[v] = true;
	for(int u: G[v])
	{
		if(vis[u])
		{
			par[v] = u;
		}
		else
		{
			dfs1(u);
			kids[v].push_back(u);
		}
	}
}

void dfswndn(int v)
{
	for(int u: kids[v])
	{
		dfswndn(u);
		wndn[v] = wndn[v] or (!wndn[u]);
	}
}

void dfswnup(int v) // wnup[v] is set
{
	bool pso = wnup[v];
	for(auto u = kids[v].rbegin(); u != kids[v].rend(); u++)
	{
		wnup[*u] = pso;
		pso = pso or (!wndn[*u]);
	}
	pso = wnup[v];
	for(int u: kids[v])
	{
		wnup[u] = !(wnup[u] or pso);
		pso = pso or (!wndn[u]);
	}
	for(int u: kids[v])
		dfswnup(u);
}

void dfscrdn(int v)
{
	for(int u: kids[v])
		dfscrdn(u);
	crdn[v] = !wndn[v];
	if(!wndn[v])
	{
		for(int u: kids[v])
			crdn[v] += crdn[u];
	}
	else
	{
		int lc = 0;
		int cr = 0;
		for(int u: kids[v])
		{
			lc += !wndn[u];
			if(!wndn[u])
				cr += crdn[u];
		}
		if(lc == 1)
			crdn[v] += cr;
	}
}

void dfscrup(int v) // crup[v] is set
{
	vector<int> rlc(kids[v].size());
	vector<int> llc(kids[v].size());
	vector<int> rls(kids[v].size());
	vector<int> lls(kids[v].size());
	vector<int> rsum(kids[v].size());
	vector<int> lsum(kids[v].size());
	int lc = 0;
	int ls = 0;
	int s = 0;
	for(int i = 0; i < (int)(kids[v].size()); i++)
	{
		int u = kids[v][i];
		llc[i] = lc;
		lls[i] = ls;
		lsum[i] = s;
		lc += !wndn[u];
		ls += (!wndn[u]) * crdn[u];
		s += crdn[u];
	}
	lc = 0;
	ls = 0;
	s = 0;
	for(int i = (int)(kids[v].size()) - 1; i >= 0; i--)
	{
		int u = kids[v][i];
		rlc[i] = lc;
		rls[i] = ls;
		rsum[i] = s;
		lc += !wndn[u];
		ls += (!wndn[u]) * crdn[u];
		s += crdn[u];
	}
	for(int i = 0; i < (int)(kids[v].size()); i++)
	{
		int u = kids[v][i];
		if(wnup[u])
		{
			crup[u] = crup[v] + lsum[i] + rsum[i];
		}
		else
		{
			crup[u] = 1;
			if(llc[i] + rlc[i] + wnup[v] == 1)
				crup[u] += (wnup[v] * crup[v]) + lls[i] + rls[i];
		}
	}
	for(int u: kids[v])
		dfscrup(u);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, D; cin >> n >> D;
	for(int i = 1; i < n; i++)
	{
		int x, y; cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(0);
	dfswndn(0);
	wnup[0] = false;
	dfswnup(0);
	dfscrdn(0);
	crup[0] = 1;
	dfscrup(0);
	for(int v = 0; v < n; v++)
	{
		finwn[v] = wndn[v] or wnup[v];
		if(finwn[v])
		{
			int lc = 0;
			int ls = 0;
			for(int u: kids[v])
			{
				lc += !wndn[u];
				ls += (!wndn[u]) * crdn[u];
			}
			lc += wnup[v];
			ls += wnup[v] * crup[v];
			if(lc == 1)
				fincr[v] = ls;
		}
		else
		{
			fincr[v] = crdn[v] + crup[v] - 1;
		}
	}
	ll E = 0;
	ll L = 0;
	for(int i = 0; i < n; i++)
	{
		L += (!finwn[i]);
		if(finwn[i])
			E += fincr[i];
		else
			E -= fincr[i];
	}
	mat them(2, 2, false);
	mat init(2, 1, false);
	them[0][0] = n*n % mod;
	them[0][1] = 0;
	them[1][0] = n*n % mod;
	them[1][1] = E;
	init[0][0] = L;
	init[1][0] = L;
	them = mpow(them, D-1);
	init = them * init;
	ll L0 = init[1][0];
	//cerr << L << " " << E << " " << L0 << endl;
	//cerr << bpow(n, 2*D) << endl;
	ll ans = 1ll * fincr[0] * L0 % mod;
	//cerr << ans << endl;
	if(finwn[0])
		ans = (bpow(n, 2*D) - ans + mod) % mod;
	cout << ans << endl;
	return 0;
}

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