Submission #19928

#	Time	Username	Problem	Language	Result	Execution time	Memory
19928		Qwaz	트리 (kriii4_X)	C++98	100 / 100	554 ms	28136 KiB

X

#include <iostream>
#include <map>
#include <vector>
using namespace std;

typedef long long ll;

const ll mod = 1000000007LL;

map< int, vector<int> > neigh;
map< int, bool > vis;
vector<int> special_vertices;

int times_mod(int a, int b, ll mod) {
	return ll(a) * ll(b) % mod;
}

// solves a*x + b*y = d = gcd(a, b)
// if d == 1, x is a modular inverse of a mod b
void extended_gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(a < 0) {extended_gcd(-a, b, d, x, y); x *= -1; return;}
    if(b < 0) {extended_gcd(a, -b, d, x, y); y *= -1; return;}
	x = 0, y = 1;
	ll lx = 1, ly = 0, frac, tmp;
	while(b)
	{
		frac = a / b; 
		tmp = a; a = b; b = tmp % b;
		tmp = x; x = lx - frac * x; lx = tmp;
		tmp = y; y = ly - frac * y; ly = tmp;
	}
	x = lx; y = ly; d = a;
}

// calculates x^-1 mod a
ll inv_mod(ll x, ll a)
{
    ll res, y, d;
    extended_gcd(x, a, d, res, y);
    return ((res % a) + a) % a;
}

ll pow_mod(ll a, ll b, ll n)
{
    if(b < 0) return inv_mod(pow_mod(a, -b, n), n);
	ll t, result = 1;
	for(t = a % n; b; t = times_mod(t, t, n), b >>= 1)
		if(b & 1) result = times_mod(result, t, n);

	return result;
}

void dfs(int v, int &num_vertex, int &sum_deg) {
	vis[v] = true;
	num_vertex++;
	vector<int> &vneigh = neigh[v];
	for (int i = 0; i < int(vneigh.size()); i++) {
		int u = vneigh[i];
		if(!vis[u])
			dfs(u, num_vertex, sum_deg);
		sum_deg++;
	}
}

int n, m;

int main() {
	cin >> n >> m;
	while(m--) {
		int a, b;
		cin >> a >> b;
		neigh[a].push_back(b);
		neigh[b].push_back(a);
		special_vertices.push_back(a);
		special_vertices.push_back(b);
	}

	int c = n;
	vector<int> e;
	for (int i = 0; i < int(special_vertices.size()); i++) {
		int v = special_vertices[i];
		if (!vis[v]) {
			int num_vertex = 0, sum_deg = 0;
			dfs(v, num_vertex, sum_deg);
			if (2 * (num_vertex - 1) != sum_deg) {
				cout << 0 << endl;
				return 0;
			}

			c -= (num_vertex - 1);
			e.push_back(num_vertex);
		}
	}

	/*
	cout << c << endl;
	for (int i = 0; i < int(e.size()); i++)
		cout << e[i] << " ";
	cout << endl;
	*/

	if (c == 1)
		cout << 1 << endl;
	else {
		int ans = pow_mod(n, c - 2, mod);
		for (int i = 0; i < int(e.size()); i++)
			ans = times_mod(ans, e[i], mod);
		cout << ans << endl;
	}

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91