백준 6150번: Summing Sums

https://www.acmicpc.net/problem/6150

6150번: Summing Sums

---

오랜만에 블로그에 연재합니다.

 

기본 골자는 초기에 주어지는 $N$개의 숫자가 다음 process를 거쳐 변환됩니다.

 

1. $N$개의 숫자에 대해, 자기 자신을 뺀 $N-1$개 숫자의 합을 $N$번 계산합니다.
2. (1)에서 계산한 숫자들로 $N$개의 숫자를 replace합니다.

해당 process를 T번 반복하는 것이 문제의 끝입니다.

 

사실은 예제에서 충분히 친절하게 T 에 따른 각 원소들의 상태를 보여주고 있습니다.

 

아마도 지문 안 읽고 예제 설명만 주의깊게 관찰해도 규칙을 알 수 있었을 것입니다.

 

---

그런데 문제에서 $0 \leq C_{i} < 9 \times 10^{7}$ 을 제시했으므로

 

특정 $C_{i}$ 값에 대한 규칙을 찾는 것이 사실상 불가능합니다.

 

따라서 각 $T$ 값마다 각 $C_{i}$ 가 몇 번 더해지는지가 중요해집니다.

 

저는 이에 따라 coefficient들의 vector을 구상했습니다.

 

이는 곧 $T$ 값과 인덱스에 따라 바뀌는 $N$ 차원의 vector가 될 것입니다.

 

예제를 통해 설명하겠습니다. $\left ( N = 3 \right )$

 

$C_{i} \left ( T \right )$ : $T$ 의 값에 따른 $C_{i}$ 의 값

 

$V_{i} \left ( T \right )$ : $T$ 의 값에 따른 coefficient vector

 

이때 $ \; C_{i} \left ( T \right ) = V_{i} \left ( T \right ) \cdot \left \langle C_{0} \; C_{1} \; C_{2} \; \cdots \; C_{N-1} \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 0$

 

$V_{0} \left ( 0 \right ) = \left \langle 1 \; 0 \; 0 \right \rangle$

$V_{1} \left ( 0 \right ) = \left \langle 0 \; 1 \; 0 \right \rangle$

$V_{2} \left ( 0 \right ) = \left \langle 0 \; 0 \; 1 \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 1$

 

$V_{0} \left ( 1 \right ) = \left \langle 0 \; 1 \; 1 \right \rangle$

$V_{1} \left ( 1 \right ) = \left \langle 1 \; 0 \; 1 \right \rangle$

$V_{2} \left ( 1 \right ) = \left \langle 1 \; 1 \; 0 \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 2$

 

$V_{0} \left ( 2 \right ) = \left \langle 2 \; 1 \; 1 \right \rangle$

$V_{1} \left ( 2 \right ) = \left \langle 1 \; 2 \; 1 \right \rangle$

$V_{2} \left ( 2 \right ) = \left \langle 1 \; 1 \; 2 \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 3$

 

$V_{0} \left ( 3 \right ) = \left \langle 2 \; 3 \; 3 \right \rangle$

$V_{1} \left ( 3 \right ) = \left \langle 3 \; 2 \; 3 \right \rangle$

$V_{2} \left ( 3 \right ) = \left \langle 3 \; 3 \; 2 \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 4$

 

$V_{0} \left ( 4 \right ) = \left \langle 6 \; 5 \; 5 \right \rangle$

$V_{1} \left ( 4 \right ) = \left \langle 5 \; 6 \; 5 \right \rangle$

$V_{2} \left ( 4 \right ) = \left \langle 5 \; 5 \; 6 \right \rangle$

 

$\left ( 1 \right ) \; T \; = \; 5$

 

$V_{0} \left ( 5 \right ) = \left \langle 10 \; 11 \; 11 \right \rangle$

$V_{1} \left ( 5 \right ) = \left \langle 11 \; 10 \; 11 \right \rangle$

$V_{2} \left ( 5 \right ) = \left \langle 11 \; 11 \; 10 \right \rangle$

 

이제 규칙이 보이시나요?

 

$V_{i} \left ( T \right )$ 의 각 원소들을 관찰하면 큰 숫자와 작은 숫자들만이 반복되고 있습니다.

 

이제 표를 통해 이 큰 숫자(Big)과 작은 숫자(Small)의 관점으로 예제를 분석해보겠습니다.

 

T	Big	Small	비고
0	1	0
1	1	0
2	2	1	Big 2배 상승
3	3	2	Small 2배 상승
4	6	5	Big 2배 상승
5	11	10	Small 2배 상승

 

여기서 추가적으로 관찰할 성질들이 있습니다.

 

1. Big이 2배 커지면 Small은 $Big - 1$
2. Small이 2배 커지면 Big은 $Small + 1$
3. $V_{i} \left ( T \right )$ 의 형태는 $\left\{\begin{matrix} Big-Major & \left ( T \;\; is \;\; odd \right ) \\ Small-Major & \left ( T \;\; is \;\; even \right ) \end{matrix}\right.$

 

여기서 Big-Major, Small-Major의 의미는 다음과 같습니다.

 

1. Big-Major : $V_{i}$ 의 $i-th \; element$ 만이 Small, 나머지가 Big
2. Small-Major : Big-Major 의 반대

---

 

그러면 우리가 규칙을 잘 찾은 걸까요? 이를 확인하기 위해, $N=4$, $N=5$ 일 때를 확인해야 합니다!

 

$\left ( N \; = \; 4 \; , \; T \; = \; 0 \right )$

 

$V_{0} \left ( 0 \right ) = \left \langle 1 \; 0 \; 0 \; 0 \right \rangle$

$V_{1} \left ( 0 \right ) = \left \langle 0 \; 1 \; 0 \; 0 \right \rangle$

$V_{2} \left ( 0 \right ) = \left \langle 0 \; 0 \; 1 \; 0 \right \rangle$

$V_{3} \left ( 0 \right ) = \left \langle 0 \; 0 \; 0 \; 1 \right \rangle$

 

$\left ( N \; = \; 4 \; , \; T \; = \; 1 \right )$

 

$V_{0} \left ( 1 \right ) = \left \langle 0 \; 1 \; 1 \; 1 \right \rangle$

$V_{1} \left ( 1 \right ) = \left \langle 1 \; 0 \; 1 \; 1 \right \rangle$

$V_{2} \left ( 1 \right ) = \left \langle 1 \; 1 \; 0 \; 1 \right \rangle$

$V_{3} \left ( 1 \right ) = \left \langle 1 \; 1 \; 1 \; 0 \right \rangle$

 

$\left ( N \; = \; 4 \; , \; T \; = \; 2 \right )$

 

$V_{0} \left ( 2 \right ) = \left \langle 3 \; 2 \; 2 \; 2 \right \rangle$

$V_{1} \left ( 2 \right ) = \left \langle 2 \; 3 \; 2 \; 2 \right \rangle$

$V_{2} \left ( 2 \right ) = \left \langle 2 \; 2 \; 3 \; 2 \right \rangle$

$V_{3} \left ( 2 \right ) = \left \langle 2 \; 2 \; 2 \; 3 \right \rangle$

 

$\left ( N \; = \; 4 \; , \; T \; = \; 3 \right )$

 

$V_{0} \left ( 3 \right ) = \left \langle 6 \; 7 \; 7 \; 7 \right \rangle$

$V_{1} \left ( 3 \right ) = \left \langle 7 \; 6 \; 7 \; 7 \right \rangle$

$V_{2} \left ( 3 \right ) = \left \langle 7 \; 7 \; 6 \; 7 \right \rangle$

$V_{3} \left ( 3 \right ) = \left \langle 7 \; 7 \; 7 \; 6 \right \rangle$

 

$\left ( N \; = \; 4 \; , \; T \; = \; 4 \right )$

 

$V_{0} \left ( 4 \right ) = \left \langle 21 \; 20 \; 20 \; 20 \right \rangle$

$V_{1} \left ( 4 \right ) = \left \langle 20 \; 21 \; 20 \; 20 \right \rangle$

$V_{2} \left ( 4 \right ) = \left \langle 20 \; 20 \; 21 \; 20 \right \rangle$

$V_{3} \left ( 4 \right ) = \left \langle 20 \; 20 \; 20 \; 21 \right \rangle$

 

이쯤에서 우리는 $N=4$ 라는 경우의 $Big-Small$ 표를 그려볼 수 있습니다.

 

T	Big	Small	비고
0	1	0
1	1	0
2	3	2	Big 3배 상승
3	7	6	Small 3배 상승
4	21	20	Big 3배 상승

흥미로운 것은, 여기서도 $Big$ 값과 $Small$ 값의 관계 (+1 또는 -1)는 유지됐다는 것입니다.

---

 

이제 $N=5$ 의 경우를 알아보겠습니다.

 

$\left ( N \; = \; 5 \; , \; T \; = \; 0 \right )$

 

$V_{0} \left ( 0 \right ) = \left \langle 1 \; 0 \; 0 \; 0 \; 0 \right \rangle$

$V_{1} \left ( 0 \right ) = \left \langle 0 \; 1 \; 0 \; 0 \; 0 \right \rangle$

$V_{2} \left ( 0 \right ) = \left \langle 0 \; 0 \; 1 \; 0 \; 0 \right \rangle$

$V_{3} \left ( 0 \right ) = \left \langle 0 \; 0 \; 0 \; 1 \; 0 \right \rangle$

$V_{4} \left ( 0 \right ) = \left \langle 0 \; 0 \; 0 \; 0 \; 1 \right \rangle$

 

$\left ( N \; = \; 5 \; , \; T \; = \; 1 \right )$

 

$V_{0} \left ( 1 \right ) = \left \langle 0 \; 1 \; 1 \; 1 \; 1 \right \rangle$

$V_{1} \left ( 1 \right ) = \left \langle 1 \; 0 \; 1 \; 1 \; 1 \right \rangle$

$V_{2} \left ( 1 \right ) = \left \langle 1 \; 1 \; 0 \; 1 \; 1 \right \rangle$

$V_{3} \left ( 1 \right ) = \left \langle 1 \; 1 \; 1 \; 0 \; 1 \right \rangle$

$V_{4} \left ( 1 \right ) = \left \langle 1 \; 1 \; 1 \; 1 \; 0 \right \rangle$

 

$\left ( N \; = \; 5 \; , \; T \; = \; 2 \right )$

 

$V_{0} \left ( 2 \right ) = \left \langle 4 \; 3 \; 3 \; 3 \; 3 \right \rangle$

$V_{1} \left ( 2 \right ) = \left \langle 3 \; 4 \; 3 \; 3 \; 3 \right \rangle$

$V_{2} \left ( 2 \right ) = \left \langle 3 \; 3 \; 4 \; 3 \; 3 \right \rangle$

$V_{3} \left ( 2 \right ) = \left \langle 3 \; 3 \; 3 \; 4 \; 3 \right \rangle$

$V_{4} \left ( 2 \right ) = \left \langle 3 \; 3 \; 3 \; 3 \; 4 \right \rangle$

 

$\left ( N \; = \; 5 \; , \; T \; = \; 3 \right )$

 

$V_{0} \left ( 3 \right ) = \left \langle 12 \; 13 \; 13 \; 13 \; 13 \right \rangle$

$V_{1} \left ( 3 \right ) = \left \langle 13 \; 12 \; 13 \; 13 \; 13 \right \rangle$

$V_{2} \left ( 3 \right ) = \left \langle 13 \; 13 \; 12 \; 13 \; 13 \right \rangle$

$V_{3} \left ( 3 \right ) = \left \langle 13 \; 13 \; 13 \; 12 \; 13 \right \rangle$

$V_{4} \left ( 3 \right ) = \left \langle 13 \; 13 \; 13 \; 13 \; 12 \right \rangle$

 

이제 $N=5$ 의 $Big-Small$ 표를 그려보겠습니다.

 

T	Big	Small	비고
0	1	0
1	1	0
2	4	3	Big 4배
3	13	12	Small 4배

 

---

이 시점에서 결국 나열을 넘어서 일반화를 해야할 것 같습니다.

 

위의 $N$ 값에 따른 경향을 살폈을 때 다음을 생각할 수 있을 것 같습니다.

 

T	$B_{T}$	$S_{T}$	비고
0	$B_{0}=1$	$S_{0}=0$	Small Major
1	$B_{1}=S_{0}\times \left ( n-1 \right ) + 1$	$S_{1}=S_{0}\times \left ( n-1 \right )$	Big Major
2	$B_{2}=B_{1}\times \left ( n-1 \right )$	$S_{2}=B_{1}\times \left ( n-1 \right ) - 1$	Small Major
3	$B_{3}=S_{2}\times \left ( n-1 \right ) + 1$	$S_{3}=S_{2}\times \left ( n-1 \right )$	Big Major

 

여기서 $B_{T}$와 $S_{T}$는 각각 $T$ 에 따른 $Big$과 $Small$입니다.

 

이로써 드디어, $N$ 값과 $T$ 값에 따른 coefficient vector 을 얻을 수 있었습니다!

 

그 말은, 이제 $N$ 값과 $T$ 값에 따라서 $C_{i}$ 를 구할 수 있다는 것입니다. 이는 다음과 같습니다.

 

$C_{i} \left ( T \right ) \; = \; \left\{\begin{matrix} C_{i} \left ( 0 \right ) + S_{2k}\sum_{i=0}^{N-1} C_{i} \left ( 0 \right ) & \left ( T \; = \; 2k \right ) \\ -C_{i} \left ( 0 \right ) + B_{2k+1} \sum_{i=0}^{N-1} C_{i} \left ( 0 \right ) & \left ( T \; = \; 2k+1 \right ) \end{matrix}\right.$

 

---

이 시점에서 $O \left ( T \right )$ 에 $B_{T}$ 와 $S_{T}$ 을 구할 수 있습니다.

 

더 빨리 구하려면 어떻게 할 수 있을까요?

 

다음 두 방정식을 풀어봄으로써, 우리는 matrix 의 exponentiation 으로 $B_{T}$ 와 $S_{T}$ 을 구할 수 있게 됩니다.

 

$\left ( 1 \right ) \begin{bmatrix} B_{2k+1} & 0 \\ S_{2k+1} & 0 \end{bmatrix} \; = \; \begin{bmatrix} x1 & y1 \\ z1 & w1 \end{bmatrix} \begin{bmatrix} B_{2k} & 0 \\ S_{2k} & 0 \end{bmatrix}$

 

$\left ( 2 \right ) \begin{bmatrix} B_{2k+2} & 0 \\ S_{2k+2} & 0 \end{bmatrix} \; = \; \begin{bmatrix} x2 & y2 \\ z2 & w2 \end{bmatrix} \begin{bmatrix} B_{2k+1} & 0 \\ S_{2k+1} & 0 \end{bmatrix}$

 

위 2개 방정식을 풀게 되면 다음을 얻습니다.

 

$x1 \; = \; 1 \; , \; y1 \; = \; N-2 \; , \; z1 \; = \; 0 \; , \; w1 \; = \; N-1$

 

$x2 \; = \; N-1 \; , \; y2 \; = \; 0 \; , \; z2 \; = \; N-2 \; , \; w2 \; = \; 1$

 

---

 

이제 $T \geq 1$ 에 대해 천천히 나열해보겠습니다.

 

$T \; = \; 1: \;\; \begin{bmatrix} B_{1} & 0 \\ S_{1} & 0 \end{bmatrix} \; = \; \begin{bmatrix} 1 & N-2 \\ 0 & N-1 \end{bmatrix} \begin{bmatrix} B_{0} & 0 \\ S_{0} & 0 \end{bmatrix}$

 

$T \; = \; 2: \;\; \begin{bmatrix} B_{2} & 0 \\ S_{2} & 0 \end{bmatrix} \; = \; \begin{bmatrix} N-1 & 0 \\ N-2 & 1 \end{bmatrix} \begin{bmatrix} 1 & N-2 \\ 0 & N-1 \end{bmatrix} \begin{bmatrix} B_{0} & 0 \\ S_{0} & 0 \end{bmatrix}$

 

$T \; = \; 3: \;\; \begin{bmatrix} B_{3} & 0 \\ S_{3} & 0 \end{bmatrix} \; = \; \begin{bmatrix} N-1 & 0 \\ N-2 & 1 \end{bmatrix} \begin{bmatrix} 1 & N-2 \\ 0 & N-1 \end{bmatrix} ^{2} \begin{bmatrix} B_{0} & 0 \\ S_{0} & 0 \end{bmatrix}$

 

$T \; = \; 4: \;\; \begin{bmatrix} B_{4} & 0 \\ S_{4} & 0 \end{bmatrix} \; = \; \begin{bmatrix} N-1 & 0 \\ N-2 & 1 \end{bmatrix} ^{2} \begin{bmatrix} 1 & N-2 \\ 0 & N-1 \end{bmatrix} ^{2} \begin{bmatrix} B_{0} & 0 \\ S_{0} & 0 \end{bmatrix}$

 

$\vdots$

 

$\begin{bmatrix} B_{T} & 0 \\ S_{T} & 0 \end{bmatrix} \; = \; \begin{bmatrix} N-1 & 0 \\ N-2 & 1 \end{bmatrix} ^{ \frac{T}{2} } \begin{bmatrix} 1 & N-2 \\ 0 & N-1 \end{bmatrix} ^{ \frac{T+1}{2} } \begin{bmatrix} B_{0} & 0 \\ S_{0} & 0 \end{bmatrix}$

 

---

 

여기까지 따라왔다면, 이제 $O \left ( log^{2}T \right )$ 라는 복잡도로 정답을 구할 수 있게 됩니다.

 

다음은 정답 코드입니다.

#include <stdio.h>
#define mod 98765431

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size);
Matrix matrix_power_modular (int power, Matrix A, int size);

long long cows[50000];

int main() {
	
	int N, T;
	scanf("%d %d", &N, &T);
	
	if (N == 1)
	{
		printf("0");
		return 0;
	}
    
	if (N == 2)
	{
		int C0, C1;
		scanf("%d %d", &C0, &C1);
		
		if (T % 2)
		{
			printf("%d %d", C1, C0);
		}
		else
		{
			printf("%d %d", C0, C1);
		}
		return 0;
	}
	
	int cowsum = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%lld", &cows[i]);
		cows[i] %= mod;
		cowsum = (cowsum + cows[i]) % mod;
	}
	
	long long NUM1 = (long long)(N - 1) * (N - 2) % mod;
	long long NUM2 = (long long)(N - 2) * (N - 2) % mod;
	NUM2 = (NUM2 + (N - 1)) % mod;
	Matrix coef =
	{{
		{N - 1, NUM1},
		{N - 2, NUM2}
	}};
	coef = matrix_power_modular(T / 2, coef, 2);
	
	if (T % 2)
	{
		Matrix temp = { {{1,N-2},{0,N-1}}};
		coef = matrix_multiply_modular(temp, coef, 2);
	}
	
	long long base = cowsum * (T % 2 ? coef.array[0][0] : coef.array[1][0]) % mod;
	
	if (T % 2)
	{
		for (int i = 0; i < N; i++)
		{
			printf("%lld\n", (-cows[i] + base + mod) % mod);
		}
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			printf("%lld\n", (base + cows[i]) % mod);
		}
	}
    
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size)
{
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++)
	{
		for (int k = 0; k < size; k++)
		{
			for (int j = 0; j < size; j++)
			{
				result.array[i][j] = (result.array[i][j] + A.array[i][k] * B.array[k][j]) % mod;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (int power, Matrix A, int size)
{
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++)
	{
		result.array[i][i] = 1;
	}
	while (power)
	{
		if (power % 2)
		{
			result = matrix_multiply_modular (result, A, size);
		}
		A = matrix_multiply_modular (A, A, size);
		power /= 2;
	}
	return result;
}

(C11, 1504KB, 0ms, 제출번호 34258432)

---

이 문제는 실제로 A4 4페이지 가량의 관찰 후에 코드를 작성했습니다.

 

그래서 그런지, 관찰할 때 기록한 종이가 남아있어선지, 실제로는 2달 전에 풀었던 문제인데도 기억이 선명하네요.

 

$Big$ 과 $Small$ 만 나타난다는 점을 증명할 수도 있겠지만, 굳이 싣지는 않겠습니다.

 

좀 더 고민하면 복잡도를 $O \left ( logT \right )$ 으로 떨굴 수 있을 것 같은데, 잘 모르겠습니다.