https://www.acmicpc.net/problem/20932
문제요약
- n개의 숫자가 주어짐(1 ~ 9, 16개)
- n - 1개로 순열을 만들고 그대로 숫자가 됨
- 남아있는 마지막 숫자가 순열로 만든 숫자의 약수일 확률 구하기
접근법
- 순열을 다 구해서 일일이 나누는건 힘듬 : 16!
- n이 16이므로 비트마스킹을 할 수 있을 것 같음
- [k개원소를선택][a][b] : k개의 원소를 선택해서 숫자를 만든 것들 중에서 a로 나누었을때 나머지가 b인 것들의 개수
- 이후 저 값을 점점 확장해나가면서 모든 경우의 수를 구해나간다
- 1 3 4 .. 7 에 8을 붙이는 경우를 생각해보자
- 합쳐지는 숫자는 1 3 4 .. 7 8 이 될 것이고 이 숫자를 9로 나눈다고 생각하고, 나누는 과정을 생각해보면
- 앞에서 부터 나눠가다보면 1 3 4 .. 7 까지를 나누고 나머지가 나올 것임. 예를 들어 5라고 하면
- 최종할 일은 5 8 나누기 9가 되는 형태임 즉 앞선 숫자까지의 "나머지"만 알고 있으면 됨 ==> b
- 추가로 어떤 숫자로 나누었을때 나머지인지 알고 있으면 됨 ==> a
- 추가로 앞에 숫자들의 조합이 무엇이었는지 알고 있으면 됨 ==> k개의 원소 선택
- 정리하면 k개의 서로 원소로 많은 순열을 만들어 낼 수 있을것이고(k!개), 최종적으로 나머지만 잘 유지하면 되는데, 어떤 숫자로 나눌지 모르니 1 ~ 9까지로 나누었을때 나머지를 잘 기억해둠
- 이런 기록을 해두었을때 최종으로 구할 값은 n - 1 개로 구성된 것들에서(마지막 숫자를 제외하고 구성을 해야하므로) 마지막 숫자로 나누었을때 나머지가 0인 것들의 합을 구하고
- 전체 경우의 수로 나누면 됨(n!)
- 비트의 개수를 확장시켜 나가는 구현을 위해서 000, 001, 010, 100, 011, 101, .... 111
- vt배열과 vector를 적절히 섞어서구현했음(최초 방문일 경우에만 vector에 추가하고, vector에 있는 것들로 다음 탐색을 하는....bfs비슷한)
newbieski