백준 문제풀이
백준 20669 - Close to You [Python]
Vermeil
2022. 4. 24. 21:53
https://www.acmicpc.net/problem/20669
20669번: Close to You
임베디드 개발자인 진우는 방구석에서 데이터 시트만 보며 허무한 학창 시절을 보냈다. 하지만 주변 친구들의 수많은 구원의 손길 끝에, 소개팅에서 만난 한콩이와 장거리 연애를 시작했다! 모
www.acmicpc.net
[알고리즘 분류]
수학
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=gt7461&logNo=110151975370
인접행렬과 인접행렬의 거듭제곱
(문제) 아래 그래프의 꼭짓점 P에서 R까지 3개의 변을 거쳐가는 모든 방법의 수는? ※ 이산수학에서 '그...
blog.naver.com
이 글을 참고하였다.
(N + 1) -> P 간선과
Q -> (N + 2) 간선들을 추가하면,
(N + 1) -> (N + 2)로 가는 길이 3~(k+2)의 경로의 개수를 구하는 문제로 볼 수 있다. 이때, (N + 2) -> (N + 2) 간선을 추가한다면, 어떤 시점 t에서 t 이하의 길이의 경로의 개수들을 합쳐줄 수 있다.
76줄부터 보면 된다.
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
import random
import sys, math
import heapq
from dataclasses import dataclass
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
hqp = heapq.heappop
hqs = heapq.heappush
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
# gcd, lcm
def gcd(x, y):
while y:
x, y = y, x % y
return x
def lcm(x, y):
return x * y // gcd(x, y)
# prime
def isPrime(x):
if x <= 1: return False
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
# Union Find
# p = [i for i in range(272727)]
def find(x):
if x == p[x]:
return x
p[x] = find(p[x])
return p[x]
def union(x, y, s):
x = find(x)
y = find(y)
if x != y:
p[y] = x
def getPow(a, x):
ret = 1
while x:
if x & 1:
ret = (ret * a) % MOD
a = (a * a) % MOD
x >>= 1
return ret
############ Main! #############
MOD = 1000000007
def mat_mul(A, B):
ret = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
for i in range(n + 2):
for j in range(n + 2):
for k in range(n + 2):
ret[i][j] += A[i][k] * B[k][j] % MOD
ret[i][j] %= MOD
return ret
def mat_exp(A, k):
while k:
if k == 1:
return A
elif k & 1:
ret = mat_exp(A, k - 1)
return mat_mul(ret, A)
else:
ret = mat_exp(A, k // 2)
return mat_mul(ret, ret)
n, m, k = mip()
a = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
for i in range(m):
x, y = mip()
x -= 1
y -= 1
a[x][y] += 1
a[y][x] += 1
p, q = mip()
P = lmip()
Q = lmip()
for i in P:
a[n][i - 1] += 1
for i in Q:
a[i - 1][n + 1] += 1
a[n + 1][n + 1] = 1
print(mat_exp(a, k + 2)[n][n + 1] - mat_exp(a, 2)[n][n + 1])
######## Priest greedev ########
|
cs |
