문자열 수를 10진법으로 바꾸는 테크닉2 - n을 n번 이어붙인 정수

D - 88888888 (atcoder.jp) D - 88888888AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n을 n번 이어붙였을때, 그것을 998244353으로 나눈 나머지를 구하는 문제 숫자를 이어붙인 문제는... 한번 10진법으로 바꿔보면 해결법이 보이는 경우가 있다 https://deepdata.tistory.com/1235 문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든D - Another Sigma Problem (atcoder.jp) D - Another..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 9. 8.
• 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

n차 다항식 함숫값 빠르게 계산하기(페르마의 소정리로 거듭제곱 빠르게 계산하기)

1. 문제 25025번: 다항식 계산 (acmicpc.net) 25025번: 다항식 계산 첫 번째 줄에 두 정수 $N$, $P$ ($0 ≤ N ≤ 10^6$, $1 ≤ P ≤ 10^3$, $P$는 소수)가 공백 하나로 구분되어 주어진다. 두 번째 줄에는 $N+1$개의 정수 $a_N$, $\cdots$, $a_1$, $a_0$ ($0 ≤ a_i ≤ 10^9$)가 공백 하나로 www.acmicpc.net 2. 풀이 결국에 구해야하는 값은 $a_{i}k^{i} mod P$이고 k와 P가 서로소이므로 페르마의 소정리를 이용할 수 있다. 그런데 1초안에 P개의 값을 계산해야하니 이거 쉽지 않다 계수는 최악의 경우 $10^{6}$개이고.. 매 함숫값마다 이들을 모두 순회해야하니.. $O(10^{9})$는 돌아야겠는..

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