dwhylee   2달 전

처음에 중복순열? 로 생각해서 comb 로 풀었더니 틀려서 고칠 방법을 못 찾아서. 

dp로 짜기위해서 수를 계산해보니

0 1 2 3 4 5.. 200
0 1 3 6 10 15   20000
0 1 4 10 20 35   1353400

이런 형태가 나오는걸 알았고 dp로 풀었습니다.

중복순열의 식으로는 왜 틀리는지 궁금하네요 ㅜㅜ 결과값이 다르게 나오는걸 봐선

곱하기/ 나누기 할때 문제가 생기는 것 같은 짐작은 되지만, 정확히는 모르겠어서 질문 올립니다. 


tols91   2달 전

음.. 나누기는 모듈러 연산 할 때 다르게 해야 한다고 알고있어요

dwhylee   2달 전

tols91 다르게 라는 것은 어떻게 하는건가요?ㅁ?

qja0950   2달 전

예를들어 12를  2로 나누는 과정에서 MOD = 10일때를 생각해보면,

실제로는 12/2 = 6이므로 6이 나와야하지만,


위의 코드같이 진행하면 (12%10)/2 = 1이 나오게 됩니다.


더 설명을 덧붙이자면, MOD M에 대해 생각할 때

gcd(a, M) = 1인 경우, aphi(M) == 1 (mod M)을 이용하면 (오일러의 정리)

b / a 하는 과정을 b * a(phi(M) - 1) 로 바꾸어서 해주시면 됩니다.

댓글을 작성하려면 로그인해야 합니다.