포함배제원리와 뫼비우스함수

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

29157번: 폭탄 피하기

 

이 문제를 읽어보면 먼과거 봤던 격자판에서의 최단경로로 이동할 수 있는 경우의 수가 문득 생각난다. 

R!C! / (R+C)! 이런 공식인데 뭔가 이를 이용한 문제인것같다. 중요한것은 성모가 모든 폭탄들을 피해서 이동한다는 것이다. 장애물이 있었을때는 해당 점 옆을 지나는 경우의 수를 세줬으면 됐는데 이 문제는 폭탄이 매우 많다.

 

그렇다면 다른 방법으로 생각을 해보자 전체 가는 경우의수에서 폭탄을 지나는 경우의 수를 빼주면 이동 가능 한 경우의 수가 나올 것이다. 하지만 단순히 빼기만 하면 될까? 폭탄이 2개 있다고 생각하면 A, B 폭탄이라고 하자.

전체경우의수 - A 폭탄지나는 경우의수 - B 폭탄 지나는 경우의수 - A,B 폭탄 지나는 경우의수

그렇다 겹치는 지점이 생긴다.

 

이를 해결하기 위한것이 포함배제의 원리이다.

 

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

16565번: N포커

해당 문제 역시 포함배제의 원리를 이용한 문제이다.

 

결론적으로는 위의 폭탄 문제를 해결하기 위해서는 포함배제의 원리를 이용하여 비트마스킹을 구현하여 지날 수 있는 폭탄은 지나고 지날 수 없는 폭탄일때는 0으로 반환하는 구현으로 해결할 수 있다. 이런점을 생각 할 수 는 있었지만

하지만 그것보다 더 큰 문제는 사실 2*10^6의 팩토리얼과 inverse를 구하는 것이다.

 

이는 나중에(언젠가) 정리해보도록하자. 검색해보면 나오지만 나로서는 이해가 가지 않았다.

 

그러면 뫼비우스함수는 뭔데?

그렇다. 저 문제를 도움받아 해결한지 얼마 안지나서 

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

1557번: 제곱 ㄴㄴ

이 문제를 해결했다는 소문을 듣고 태그를 보니 "포함 배제의 원리" 가 있었던 것이다. 그리고 이 문제의 정해역시 뫼비우스 함수 라는것을 이용하는것이었다. 

 

뫼비우스함수란

이런 형태의 그래프로

N이 소수들의 곱일때 (-1)^k  , 제곱수를 약수로 가질때 0이 되는 함수이다.

저 문제를 읽어보면 우리가 구하는 것이 M번째 제곱수로 나누어떨어지지 않는 값을 구하는것이다.

뫼비우스 함수를 어떻게 구할까? 

2^2, 3^2 그리고 

2^2 3^2 같은 수를 생각해보자. 그렇다. 이것역시 포함배제의 원리인것이다.

https://nyan101.github.io/blog/Mobius-function

https://ohgym.tistory.com/19

 

두개의 블로그를 참고했는데 이쪽들이 더 설명을 잘해놔서 정독하고 이를 이용하여 코드를짰다.

그리고 제곱ㄴㄴ수를 미리 구해놓고 이분탐색을 이용하여 K번째 제곱수를 찾는것인데

얼마나 가야 K번째 제곱ㄴㄴ수를 찾는지를 알수가없어서 많은 시도가 있었다..

하지만, 수학적인 원리로 이를 계산할수 있다는데, 아직 그정도 경지까지는 이르지못했다.