CP Algorithm 정리 (1)

올해는 CP 알고리즘을 꼭 다 습득할것!

Binary Exponentiation

Integer Power

일단은 간단한 거듭제곱 연산문제, 이진법 표기대로 더해준다고 생각하면 된다.

1
2
3
4
5
6
7
8
9
10
11
func pow(a, n int64) int64 {
	var ret, MOD int64 = 1, 1000000007
	for n > 0 {
		if n&1 != 0 {
			ret = (ret * a) % MOD
		}
		a = (a * a) % MOD
		n /= 2
	}
	return ret
}

Matrix Power

행렬의 거듭제곱도 이진 제곱으로 손쉽게 풀린다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const MOD uint64 = 1000000007
const ORDER int = 8

type Matrix [ORDER][ORDER]uint64

func mul(a, b *Matrix) *Matrix {
	z := &Matrix{}
	for i := 0; i < ORDER; i++ {
		for j := 0; j < ORDER; j++ {
			for k := 0; k < ORDER; k++ {
				z[i][j] = (z[i][j] + a[i][k]*b[k][j]) % MOD
			}
		}
	}
	return z
}

func getIdentity() *Matrix {
	ret := &Matrix{}
	for i := 0; i < ORDER; i++ {
		ret[i][i] = 1
	}
	return ret
}

func pow(a *Matrix, n uint64) *Matrix {
	ret := getIdentity()
	for n > 0 {
		if n&1 != 0 {
			ret = mul(ret, a)
		}
		a = mul(a, a)
		n /= 2
	}
	return ret
}

Power of Adjacency Matrix

인접 행렬의 거듭제곱은 A에서 B까지 갈 수 있는 경우의 수이다.