흙금이네 블로그

아이디어 모듈러 연산의 분배법칙과 페르마의 소정리로 계산식을 바꾼 후, 이분 탐색을 이용해 계산한다. 풀이 \(\binom{N}{K}\)는 \(\frac{N!}{K!(N-K)!}\)이고, \(\frac{N!}{K!(N-K)!}=\frac{N\cdot(N-1)\cdot\cdots\cdot(N-K+1)}{K!}\)이다. 결과값은 1,000,000,007로 나눈 나머지이므로 계산 과정에서 모듈러 연산의 곱셈에 대한 분배법칙을 이용할 수 있다. \((a\bmod p)\cdot(b\bmod p)=ab\bmod p\) 따라서 계산 과정에서 발생하는 중간값들을 모두 1,000,000,007로 나눈 나머지로 두고 계산할 수 있다. 모듈러 연산의 곱셈에 대한 분배법칙으로 분모와 분자를 각각 1,000,000,007로 나..

아이디어 유니온 파인드와 BFS로 두 백조가 만나는 데 걸리는 일수를 찾는다. 풀이 import sys from collections import deque input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def find(n): temp = n while group[n] != n: n = group[n] group[temp] = n return n def union(n1, n2): n1 = find(n1) n2 = find(n2) if n1 > n2: n1, n2 = n2, n1 group[n2] = n1 R, C = map(int, input().split()) board = [[*input().r..

아이디어 CCW(Counter Clock Wise)로 각 선분의 두 점과 다른 선분의 끝점의 방향들로 두 선분이 교차하는지 확인한다. 풀이 def solution(): def ccw(a, b, c): return (a[0]*b[1]+b[0]*c[1]+c[0]*a[1])-(b[0]*a[1]+c[0]*b[1]+a[0]*c[1]) x1, y1, x2, y2 = map(int, input().split()) x3, y3, x4, y4 = map(int, input().split()) p1, p2, p3, p4 = (x1, y1), (x2, y2), (x3, y3), (x4, y4) l1 = ccw(p1, p2, p3)*ccw(p1, p2, p4) l2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)..