BOJ 25917 - Prime Arrangement
약간 낚시성이 있는 문제인데, 실제로 대회땐 골드 5임에도 불구하고 적게 풀렸다고 한다.
서로 다른 소수의 곱들은 어떻게 $C$개씩 골라도 항상 다른 값을 가져 순서가 고정됨을 알 수 있다.
따라서 $A, P$ 값은 의미가 없고 $R, C$만으로 푸는 문제이다.
순서에 상관없이 $RC$개의 소수를 각각 $C$개 씩 $R$개의 집합으로 나누는 경우의 수를 센다.
정답은 $\dfrac{(RC)!}{R!}$ 이다.
소수 $RC$ 개를 아무렇게나 모두 배치하는게 $(RC)!$ 이고, $R$ 개의 행들은 모두 들어갈 자리가 정해지기 때문에 해당 배치들에서 $R!$ 을 나눠줘야 한다.
Comments