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

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 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!..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 6. 20.
• textsms

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

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 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!..

• format_list_bulleted 조합론
• · 2024. 6. 18.
• textsms

DP가 불가능할 때 특정 위치 (x,y)로 이동하는 경우의 수를 구하는 다른 방법

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..

• format_list_bulleted 조합론
• · 2024. 4. 5.
• textsms

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

이미 알고있는 것들인데 블로그에 정리가 안되어 있어서 1. n!을 소수 p로 나눈 나머지 소수 p에 대하여 $n! mod p$를 구하는 문제가 있다. 단 하나의 $n! mod p$를 구해야한다면... $n! = n*(n-1)*(n-2)*...*1$이므로, 1부터 n까지 $O(N)$에 다 곱한 다음, p로 나눈 나머지를 구하는 것이 간단하다. 하지만 n이 매우 크면서, 여러가지 n에 대한 $n! mod p$가 필요하다면 이야기가 달라진다. 여러가지 n에 대한 $n! mod p$가 필요하다면 가능한 모든 n에 대해 $n! mod p$를 구해놓고 O(1)로 접근하면 된다. 여기서 다이나믹 프로그래밍에 의해 이전에 구해놓은 값을 저장해둔다면, O(N)에 모든 n에 대해 $n! mod p$를 구할 수 있다. $n..

• format_list_bulleted 정수론
• · 2024. 4. 5.
• textsms

이항정리를 이용한 거듭제곱의 합 1^k+2^k+3^k+...+n^k 을 구하는 방법

1. 이항정리(binomial theorem) 0이상의 정수 n과 음이 아닌 정수 x,y에 대하여, $$(x+y)^{n} = \sum_{k = 0}^{n}\binom{n}{k}x^{k}y^{n-k}$$ https://en.wikipedia.org/wiki/Binomial_theorem Binomial theorem - Wikipedia From Wikipedia, the free encyclopedia Algebraic expansion of powers of a binomial In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. ..

• format_list_bulleted 정수론
• · 2023. 8. 26.
• textsms

n과 소수 p가 매우 클 때 wilson's theorem와 fermat's little theorem을 이용한 n! mod p 구하기

https://en.wikipedia.org/wiki/Wilson%27s_theorem Wilson's theorem - Wikipedia From Wikipedia, the free encyclopedia Theorem on prime numbers In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multip en.wikipedia.org https://namu.wiki/w/%EC%9C%8C%EC%8A%A8%EC%9D%9..

• format_list_bulleted 정수론
• · 2023. 8. 5.
• textsms