그래프 이론2 [백준 21117] Number of Colorful Matchings [Ruby III] https://www.acmicpc.net/problem/21117 21117번: Number of Colorful Matchings Output n+1 lines containing your answers for k=0,1,2,…,n respectively. Remember that you only need to output the answer modulo 2. www.acmicpc.net 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다. 1. 이분 그래프 G의 adjoint matrix는 \( \begin{bmatrix} O & A \ A^T & O.. 2023. 2. 6. [백준 16224] Path Equality (Diamond III) https://www.acmicpc.net/problem/16224 16224번: Path Equality N, M이 한 줄에 차례대로 입력된다. 입력은 1≤N≤500, 1≤M≤5000를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은 m≤n이고 mn이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노.. 2023. 1. 11. 이전 1 다음
