백준 25917 Prime Arrangement 파이썬 증명 X

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

문제에서 소수만 주어진 이유는 서로 다른 소수 * 소수는 값이 안 겹치기 때문이다. 여기서 알 수 있는것은 문제의 답은 나올 수 있는 모든 조합의 경우의 수인것이다. (P는 고려할 필요가 없음. 조합을 만들고 알맞게 순서를 배치만 하면 되므로)

 

처음에는 (nCc * n-cCc * n-c-cCc ... *n-c-c...-cC0) * {(c!)**r}을 해주는 방법으로 생각 했다.

하지만 예제의 답이 나오지 않았고 여러 조합으로 해본결과 

(nCr * n-rCr * n-r-rCr ... *n-r-r...-rC0) * {(r!)**c-1} 이런 방정식으로 답을 유도했다.

이 답을 유도하기위해 아래와 같은 작업을 해줬다,

 

아직 수학적 기술이 부족해 왜 (r!)**(c-1)을 해주는지 잘 모르겠다 ㅠㅠ

"""
4 4
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 59
1 2 3 4
답: 315591831
"""
def nr(n,c):#조합계산하는 함수
    ni=1
    for i in range(n,n-c,-1):
        ni*=i
    ci=1
    for i in range(1,c+1):
        ci*=i
    return ni//ci#조합 계산
    
mod = 998244353
r,c = map(int,input().split())
s = list(map(int,input().split()))
p = list(map(int,input().split()))
ls = len(s)
re = 1
while ls!=0:#조합의 경우의 수
    re*=nr(ls,r)
    ls-=r
w = 315591831#답
i = 0
while True:#이 방법을 통해 방정식을 유추함
    if (i*re)%mod==w:
        break
    i+=1
#i = 13824 = 24**3

아래는 정답코드이다.

def nr(n,c):#조합계산하는 함수
    ni=1
    for i in range(n,n-c,-1):
        ni*=i
    ci=1
    for i in range(1,c+1):
        ci*=i
    return ni//ci#조합 계산
        
mod= 998244353#나눠주기
r,c = map(int,input().split())
s = list(map(int,input().split()))
p = list(map(int,input().split()))
ls = len(s)
re=1
while ls!=0:#조합의 경우의 수
    re*=nr(ls,r)
    ls-=r
    
e = 1
for i in range(1,r+1):#행에서 자리를 섞는 경우.
    e*=i
t = (e**(c-1))#열의 개수 -1 제곱해줌
print((t*re)%mod)#결과