다이나믹 프로그래밍으로 구하는 복수순열2 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

E - Alphabet Tiles (atcoder.jp)

E - Alphabet Tiles

 

 

대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제

 

길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면..

 

이들을 일렬로 배열하는 복수순열의 개수와 같으므로, 

 

$$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!a2!...a26!}$$

 

그러면 주어진 배열 C로 만들 수 있는 가능한 모든 (a1,a2,a3,..,a26)의 조합에 대해 위 값들의 합을 구하면 된다.

 

만약, A가 2개, B가 3개, C가 4개 있을때, 길이가 9인 문자열을 만드는 방법의 수는?

 

$$\frac{9!}{2!3!4!}$$임을 알고있다.

 

https://deepdata.tistory.com/1272

다항식의 곱으로 구하는 복수순열1 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

 

 

 

이전에는 다항식의 곱으로 접근했지만... 이번에는 다음과 같이 접근해본다면..?

 

먼저 A 2개만 있다고 하고... 길이가 2인 빈자리 _ _에서 A의 자리를 선택하는 방법은 2자리에서 2자리를 뽑는 방법

 

2C2와 같다.

 

이제 A가 2개, B가 3개만 있다고 하고 길이 5인 빈자리 _ _ _ _ _에서 B의 자리를 선택하는 방법의 수는..?

 

5자리 중 3자리를 선택하면 5C3가지에 나머지 2자리는 A로 채우면 된다

 

5C3 * 2C2가지.

 

마지막으로 A가 2개, B가 3개, C가 4개 있다고 해보자.

 

길이가 9인 빈자리 _ _ _ _ _ _ _ _ _에서 C의 자리를 선택하는 방법의 수는 9C4가지이다.

 

그리고 B의 자리를 선택하는 방법의 수는 C를 선택하고 나머지 5자리 중 3자리를 선택하는 5C3이다.

 

그리고 나머지 2자리 중 A 2자리를 선택하는 방법의 수 2C2이다.

 

따라서 9C4 * 5C3 * 2C2와 같다.

 

그런데 이는 놀랍게도... 위에서 구한 복수순열 $\frac{9!}{2!3!4!}$과 같다.

 

 

 

 

따라서 다음과 같은 다이나믹 프로그래밍 방법이 유효할 수 있다.

 

dp[i][j]를 i번 알파벳까지 사용하여 길이 j까지 만드는 방법의 수라고 한다면...

 

i+1번 알파벳까지 사용하여 길이 j+r까지 만드는 방법의 수는...

 

i번 알파벳까지 사용하여 길이 j까지 만드는 방법의 수 * j+rCr이다.

 

dp[i+1][j+r] += dp[i][j] * j+rCr

 

0번 알파벳 사용하여 길이 2를 만드는 2C2에, 1번 알파벳 사용하여 길이 5를 만드는 방법은 5C3의 곱

 

1번 알파벳까지 사용하여 길이 5를 만드는 2C2*5C3에 2번 알파벳 사용하여 길이 9를 만드는 방법은 9C4의 곱

 

dp = [[0]*(k+1) for _ in range(len(C)+1)]

#길이 0을 만드는 방법은 아무것도 안하면 되니 1가지
dp[0][0] = 1

for i in range(len(C)): #사용한 알파벳 번호 0~len(C)-1

    for j in range(k+1): #길이 0 ~ k

         #해당 알파벳 사용 개수
         #전체 길이 k에서 j만큼 알파벳이 정해져있다면, 나머지 k-j만큼 사용가능
         #물론 알파벳은 C[i]개 있는데, 이게 k-j보다 더 작다면..? C[i]개만큼 사용 가능
         #C[i]가 사용 제한 k-j보다 크다면 k-j까지만 사용가능
        for r in range(min(C[i],k-j)+1):

            dp[i+1][j+r] += (dp[i][j]*c(j+r,r))
            dp[i+1][j+r] %= mod

print(sum(dp[len(C)][1:]) % mod)

   

 

따라서 정답은 모든 알파벳을 사용한 길이 1부터 길이 k까지의 합 sum(dp[len(C)][1:])이다.

 

여기서 c(j+r,r)은 j+rCr로 이항계수인데.. 빠른 계산을 위해 팩토리얼 값을 미리 구해둔다.

 

팩토리얼과 inverse factorial은 점화식으로 쉽게 구할 수 있다

 

https://deepdata.tistory.com/1151

팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

 

 

mod = 998244353

k = int(input())

C = list(map(int,input().split()))

#팩토리얼
factorial = [0]*(k+1)

factorial[0] = 1

for i in range(1,k+1):
    
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod

#inverse factorial
inverse = [0]*(k+1)

inverse[k] = pow(factorial[k],mod-2,mod)

for i in range(k-1,-1,-1):
    
    inverse[i] = inverse[i+1]*(i+1)
    inverse[i] %= mod

#이항계수 nCk
def c(n,k):
    
    return (factorial[n]*inverse[k]*inverse[n-k])% mod