[CodeForce/C++] F. Multiplicative Arrays (Div.3)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 페르마의 소정리와 DP를 이용해서 풀 수 있는 문제다.

 

잘 생각해보면 이 문제는 k를 소인수 분해하는 것으로 시작할 수 있다는 것을 알 수 있다.

왜냐하면 최대 길이 n의 배열의 곱이 k가 나오기 위해서는 배열 a의 안에 k의 약수들이 있다는 뜻이 되기 때문이다.

 

이를 이용하면 배열의 길이가 n일 때, 1을 제외한 k의 약수의 개수를 m이라고 하면 n-m개의 1과 m개의 k의 약수로 이루어진 배열의 조합을 구하는 문제로 볼 수 있다.  

 

이를 이용해 DP로 문제를 해결할 수 있다.

 

아래와 같이 DP를 정의 하자.

 

DP[k][i] = 1이 아닌 i개의 수를 곱해서 k를 만드는 경우의 수

 

그러면 i개의 약수를 길이 1~n 크기의 배열에 대해  자리를 정하는 방법을 DP[k][i]와 곱하면 k라는 수를 만들 수 있는 모든 배열의 수를 구할 수 있다.

 

ex) k가 4일때 배열의 길이가 4라고 가정하고 1이 아닌 약수의 수가 2이라고 하면 [ㅁ, ㅁ, ㅁ, ㅁ]의 자리 중 두 개의 자리가 필요하다. 그러면 4개 중 2개를 뽑는 경우이므로 4C2를 곱해주면 된다.

 

이를 요약하면, k라는 수를 만드는 방법은 아래와 같이 표현할 수 있다.

 

$$\sum\limits_{j=1}^m  \sum\limits_{i=1}^n iCj\cdot DP[k][j] $$

 

이 때, j는 1이 아닌 k의 약수의 수다.

 

여기서 k의 범위가 10^5이기 때문에 j는 최대 2^17을 넘지 못한다.

즉, 소인수 분해 했을 때, k의 1이 아닌 약수의 수는 최대 16개라는 뜻

 

$$DP[k][j+1] =   \sum DP[k/r][j] $$

또한 DP를 구하는 방법도 위와 같이 구할 수 있다.

j개의 약수로 k/r이라는 수를 만드는 경우가 있다면, r을 곱해서 k를 j+1개의 약수로 만드는 경우가 된다.

 

이제 정리해주어야할 부분이 있다.

 

$$\sum\limits_{i=1}^n iCj  = {{n+1}\choose {j+1}}$$

이 부분을 잘 생각해보면 하키공식을 이용해 위와 같이 변경해 줄 수 있다.

 

그려면 아래와 같이 변경할 수 있다.

$$\sum\limits_{j=1}^m  {{n+1}\choose {j+1}} \cdot DP[k][j] $$

 

마지막으로 nCr을 빠르게 구하기 위해 페르마의 소정리를 이용해야 한다.

 

C++에서 너무 큰 n에 대해 nCr을 구할 수 없으므로, 이를 위해 r!부분을 페르마의 소정리를 이용해 구하면

p가 소수일 경우 r! = a 라고 하면

 

$$ a^{p-2} (mod p) = a^-1 (mod p)$$

로 표현할 수 있다.

 

페르마의 소정리

 

이를 이용해 문제를 풀면 1~k에 대해 1~n 크기의 배열의 모든 원소를 곱해서 만들 수 있는 경우의 수를 구할 수 있다

 

+ p가 큰 데 이는 p/2 = p/4 *p/4 = p/8 * p/8 ... 과 같이 재귀적으로 빠르게 계산하면 된다.

 

 

Code

 

추후 추가...

---

 

코드포스를 풀다보니 문제 해석이 잘 안돼서 막히는 문제들이 많았다...

이 문제는 그런 문제는 아니였지만, 페르마의 소정리를 떠올리지 못하면 풀기 힘든 문제였다... ㅠㅠ

 

당분간은 점수보다 못 푼 문제들을 푸는 데 집중해야겠다..

 

https://codeforces.com/contest/2060/problem/F