Boj 20390) 완전그래프의 최소 스패닝트리

문제

백준 20390

설명

1. Kruskal 과 Prims(O(\(E\log{E}\))) 은 정점들을 저장해둘 필요가 있어 사용할 수 없다. 하지만 프림(O(\(V^2\))) 또는 프림(O(\(E\log{V}\))) 버전은 정점크기의 배열이면 충분하다.

2. 들어오는 숫자 범위가 CPU 곱셈을 못하게 한다. 분할정복을 통한 방법을 통해 O(자릿수) 의 시간복잡도를 가진 곱셈을 사용해보자.

3. MST 찾는 도중마다 거리를 구하는 알고리즘을 돌리면 너무 느리다. 하지만 X * A 와 X * B 는 미리 계산해둘 수 있고, 그러면 MST 에서는 덧셈만 하면 된다.

시간 복잡도

O(\(N^2\))

코드

using ll = long long;
ll A, B, C = 1000000001, D;

ll SafeMul(ll a, ll b)
{
	if (a == 0 || b == 0) return 0;
	if(b>a) swap(a,b);
	ll res = 0, mul = a;
	while (b)
	{
		if (b & 1) res = (res + mul) % C;
		mul = mul * 2 % C;
		b >>= 1;
	}
	return res;
}

ll X[10001], XA[10001], XB[10001];
int n; ll dist[10001];
bool visits[10001]; int nVisit = 0;

int main()
{
	cin >> n;
	cin >> A >> B >> C >> D;
	for (int i = 0; i < n; i++) cin >> X[i];
	for (int i = 0; i < n; i++) XA[i] = SafeMul(X[i], A) % C;
	for (int i = 0; i < n; i++) XB[i] = SafeMul(X[i], B) % C;
	
	fill(dist, dist + n, 1e18);
	dist[0] = 0;
	
	ll ans = 0;
	while (nVisit < n)
	{
		ll now_dist = 1e18; int now_idx = -1;
		for (int i = 0; i < n; i++)
			if (!visits[i] && now_dist > dist[i]) 
			{
				now_dist = dist[i]; 
				now_idx = i; 
			}
		
		assert(now_idx >= 0);
		nVisit++;
		visits[now_idx] = true;
		ans += now_dist;

		for(int i = 0; i < n; i++)
			if(!visits[i])
				dist[i] = min(dist[i], (XA[min(now_idx, i)] + XB[max(now_idx, i)]) % C ^ D );
	}
	cout << ans;
}