2^30으로 나눈 나머지로 2^5으로 나눈 나머지를 구할 수 있을까

8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 $2^{p}$로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod  문제는 최대 ..

• format_list_bulleted 정수론
• · 2024. 8. 10.
• textsms

홀수 위치 자리수들과 짝수 위치 자리수들의 곱이 서로 같은 n자리 자연수 찾는 마법같은 방법(중간에서 만나기)

14108번: Umnozak (acmicpc.net) n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제 첫번째 자리는 홀수 위치라고 가정 1자리 자연수는 홀수 위치밖에 없으니 0개 2자리 자연수는? 11,22,33,44,55,66,77,88,99로 9개 3자리 자연수는? 100부터 999까지 전수조사해보는게 나을 것 같다 count = 0for i in range(100,1000): s = str(i) a = 1 b = 1 for j in range(len(s)): if j % 2 == 0: a *= int(s[j])..

• format_list_bulleted 중간에서 만나기
• · 2024. 7. 24.
• textsms

n번째로 작은 팰린드롬 수를 찾는 놀라운 방법

https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 7. 23.
• textsms

다이나믹 프로그래밍으로 구하는 복수순열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

문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든 수의 합

D - Another Sigma Problem (atcoder.jp) D - Another Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  배열 A의 모든 순서쌍 (A[i],A[j])에 대하여 f(A[i],A[j])를 A[i]A[j]라고 정의 예를 들어 f(10,1) = 101이고 f(3,14) = 314 i  예를 들어 3 14 15라면 (3,14), (3,15), (14,15) 3개의 순서쌍에 대해 314, 315, 1415가 있고 이들의 합은 2044 모든 순서쌍을 찾는 것은 기본적으로 $O(..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 6. 11.
• textsms