cho.sh

문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 4157개
제목난이도유형정답자시간 제한메모리 제한채점
Amusement Park정점이 18개 이하인 무방향 그래프에서 각 간선을 한 방향으로 정하는 배향 중 비순환인 것(위상 순서가 존재하는 것)들에 대해, 원래 방향에서 뒤집힌 간선 수의 합을 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다3초512 MB지문만 제공
Scissors and Tape두 단순 다각형을 서로 정합되는 조각으로 자른 뒤 평행이동과 회전만으로 목표 다각형을 조립하는 해를 출력합니다.어려움9기하분할 정복+2아직 제출이 없습니다1초512 MB지문만 제공
Majorant배열에서 점 갱신이 일어나고, 각 구간 질의마다 엄격한 다수 원소가 i인 부분배열의 개수에 i를 곱한 합을 998244353으로 나눈 나머지를 구한다.어려움9세그먼트 트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
자N개의 눈금을 가진 자에서 임의의 두 눈금 사이 거리가 모두 다르도록 하면서 길이가 최소가 되는 눈금 위치를 오름차순으로 출력한다.어려움9백트래킹완전 탐색+2아직 제출이 없습니다2초512 MB채점 가능
난Lcm 길이의 난을 잘라 N명에게 나눌 때, 각자가 난 전체를 먹었을 때 행복도의 1/N 이상을 받도록 분배하는 방법이 있는지 판정하고 그 방법을 출력한다.어려움9그리디수학+2아직 제출이 없습니다3초256 MB지문만 제공
고행1부터 N까지의 순열 가운데, 각 날의 시간 구간 안에서 연속한 문장을 읽는 최적 일정으로 경전을 정확히 K일에 끝내는 순열의 개수를 센다.어려움9동적 계획법조합론+2아직 제출이 없습니다0.6초256 MB채점 가능
Broken Device안나는 고장 위치를 알지만 브루노는 모르는 상황에서, 길이 N인 비트열로 정수 X를 전달하는 부호화 방식을 설계한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
Solitaire3×N 보드의 빈 칸을 채우는 순서의 수를 구한다. 어떤 칸은 위아래 칸이 모두 채워졌거나 좌우 칸이 모두 채워졌을 때만 놓을 수 있다. 경우의 수를 1e9+7로 나눈 나머지를 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다4초512 MB지문만 제공
Building 3서로 다른 높이 순열에서 나올 수 있는 길이 N 수열 A 중, 한 원소를 지우면 주어진 수열 B가 되는 것의 개수를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초512 MB지문만 제공
메신저4x4 격자 위의 말을 두 사람이 번갈아 움직이면서, 호출 순서와 시점을 모르는 상태에서 B가 10000번의 이동 안에 비밀 값 X를 알아내도록 두 사람의 전략을 설계한다.어려움9구현시뮬레이션+2아직 제출이 없습니다2초512 MB채점 가능
별자리별자리 A와 B에 속하는 별의 집합을 정할 때, 두 집합이 각각 연결되고 선분이 서로 교차하지 않도록 하는 경우의 수를 구한다.어려움9기하조합론+2아직 제출이 없습니다1초512 MB채점 가능
그래프와 사이클홀수 개의 정점을 가진 가중 완전 그래프에서 모든 간선을 서로 겹치지 않는 사이클로 분할하고, 각 사이클에서 연속한 두 간선의 최댓값 합의 총합을 최소화한다.어려움9그래프그리디+2아직 제출이 없습니다2초256 MB채점 가능
가장 가까운 점직사각형 안의 정수 격자점 가운데 p1까지의 거리가 K개 표시점 중 최소인 점의 개수를 센다.어려움9기하분할 정복+2아직 제출이 없습니다2초512 MB채점 가능
DivModuloM이 4e18까지, D가 1.6e7까지 주어질 때 C(M,N)에서 D의 인수를 모두 제거한 뒤 D로 나눈 나머지를 구한다.어려움9수학정수론+2아직 제출이 없습니다3초1024 MB채점 가능
Tiling with T-tetrominoesN 곱하기 M 격자를 T-테트로미노로 채우는 경우의 수를 998244353으로 나눈 나머지를 구한다. 회전과 뒤집기는 서로 다른 배치로 센다. N은 10^18까지, M은 15까지 주어진다.어려움9동적 계획법행렬+2아직 제출이 없습니다0.1초256 MB지문만 제공
춤추는 원원형으로 둘러선 n명의 아이에게 이진 복장을 배정하되, 각 아이를 중심으로 한 연속 구간의 합 홀짝을 나타내는 n개의 조건을 모두 만족하는 배정의 수를 1e9+7로 나눈 나머지로 구한다.어려움9수학누적 합+2아직 제출이 없습니다2초512 MB채점 가능
트리 깊이순열의 각 구간에서 최솟값을 루트로 삼아 만든 이진 탐색 트리에서, 반전이 정확히 K개인 모든 순열에 대해 각 노드 i의 깊이 합을 구해 소수 M으로 나눈 나머지를 출력한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB채점 가능
Jaki Jovsi길이가 최대 백만인 소문자 문자열이 주어질 때, l이 증가하고 r이 감소하는 팰린드롬 부분 문자열들의 중첩 수열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9문자열동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
체스판 이동N×M 체스판에서 홀수 행은 같은 색 인접 칸으로만, 짝수 행은 색 제약 없이 인접 칸으로 이동할 수 있을 때 1행에서 N행에 도착하는 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법행렬+2아직 제출이 없습니다2초512 MB채점 가능
순례자의 기억과 감명받은 신격자 위 (1,1)에서 (N,N)으로 가는 단조 경로들이 만드는 서로 다른 0/1 문자열마다 등장 횟수 X에 대해 X^2+1을 더한 합을 구한다.어려움9동적 계획법조합론+1아직 제출이 없습니다8초1024 MB지문만 제공
N!!!...! mod PN, K와 소수 P가 주어질 때 a_0 = N, a_{n+1} = (a_n)!으로 정의된 수열의 a_K를 P로 나눈 나머지를 구한다. N, K, P는 최대 5×10^8이다.어려움9정수론수학+1아직 제출이 없습니다1초1024 MB지문만 제공
트리와 K번째 지름쿼리마다 두 정점의 번호를 맞바꾼 뒤, 트리의 모든 지름을 인코딩한 수 가운데 K번째로 작은 값을 구한다.어려움9트리수학+2아직 제출이 없습니다3초1024 MB지문만 제공
그래프 세기정점 2n개를 가진 무향 그래프 중 완전 매칭이 없지만 어떤 없는 변을 하나 추가하면 완전 매칭이 생기는 그래프의 동형류 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론그래프+2아직 제출이 없습니다5초512 MB채점 가능
Interesting Graph그래프의 임의의 7개 정점 중 두 정점이 바깥의 단절점을 지나야만 연결되도록 보장될 때, 1부터 n가지 색 각각으로 하는 적절한 색칠의 수를 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
지식문자열 s에서 aa, bbb, ababab 블록을 넣거나 지우는 연산으로 길이가 x인 문자열을 만들 수 있는 경우의 수를 구해 998244353으로 나눈 나머지를 출력한다.어려움9문자열조합론+2아직 제출이 없습니다1초512 MB채점 가능
Airplane Cliques트리와 거리 한계 x가 주어질 때, 모든 두 정점 사이의 거리가 x 이하인 k개 정점 부분집합의 개수를 각 k마다 998244353으로 나눈 나머지로 구한다.어려움9트리분할 정복+2아직 제출이 없습니다2초512 MB지문만 제공
Disjoint LIS최장 증가 부분수열을 서로 원소를 공유하지 않는 두 개의 증가 부분수열로 나타낼 수 있는 n개 원소 순열의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다2초512 MB지문만 제공
One Goal정점 n개인 트리에서 모든 k-튜플에 대해 그 튜플의 1-중앙값 중 번호가 가장 작은 정점의 번호 합을 998244353으로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Bitwise Xor고른 원소 두 개의 xor가 모두 x 이상인 비어 있지 않은 부분수열의 개수를 998244353으로 나눈 나머지로 구한다.어려움9비트 연산트라이+2아직 제출이 없습니다2초512 MB채점 가능
Counting Cactus주어진 작은 그래프(n은 13 이하)에서 부분 그래프의 변 집합 가운데 연결되어 있고 모든 변이 많아야 하나의 단순 사이클에 속하는 것의 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법그래프+2아직 제출이 없습니다2초512 MB지문만 제공
K-pop Strings길이 n인 문자열 가운데 길이가 n-k 이상인 연속 반복(tandem repeat)이 하나도 없는 문자열의 개수를 35종 문자로 세어 998244353으로 나눈 나머지를 구한다. n은 100 이하, k는 16 이하이다.어려움9동적 계획법문자열+2아직 제출이 없습니다7초512 MB지문만 제공
Four Elements정수 구간 n개의 합집합에서 원소 4개의 합이 s인 부분집합의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
Nine Judgesk개 문제에 대한 n명의 선호 순위가 주어질 때, 다수결 교환으로 이루어지는 마르코프 연쇄가 양의 확률로 무한히 자주 방문하는 p개짜리 문제 집합을 하나 출력한다.어려움9게임 이론조합론+2아직 제출이 없습니다2초512 MB지문만 제공
Eleven Problems문제 수 n이 11 이하일 때, 두 훈련 캠프의 득표 분포가 주어지면 두 원 그래프의 조각 순서를 정해 같은 문제 조각이 겹치는 면적 비율을 최대로 만든다.어려움9완전 탐색기하+2아직 제출이 없습니다2초512 MB지문만 제공
또 다른 동전 무게 재기 퍼즐저울을 m번 사용하고 각 봉지에 k개의 동전이 있을 때, 무거운 가짜 봉지를 유일하게 가려낼 수 있는 봉지 수의 최댓값을 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB채점 가능
All Kill각 문제의 풀이 아이디어가 균등분포로 임의의 분에 도착할 때, 모든 문제를 연속된 구간으로 끝까지 코딩할 확률을 t^n배 하여 998244353으로 나눈 나머지를 구한다.어려움9확률조합론+2아직 제출이 없습니다1초512 MB지문만 제공
편집 거리 세기주어진 문자열 s와 레벤슈타인 거리가 정확히 d인 'A'부터 'Z'까지의 서로 다른 문자열 개수를 998244353으로 나눈 나머지를 구한다.어려움9동적 계획법문자열+2아직 제출이 없습니다10초512 MB채점 가능
Rooted Subtrees두 루트 r과 p가 주어질 때, r을 루트로 하는 트리의 서브트리와 p를 루트로 하는 트리의 서브트리의 교집합으로 만들 수 있는 서로 다른 공집합이 아닌 집합의 개수를 구한다.어려움9트리DFS+2아직 제출이 없습니다11초512 MB채점 가능
Associativity Degreen과 여러 k가 주어질 때, 결합 법칙이 성립하는 삼중항의 개수가 정확히 k인 이항 연산을 구성하거나 불가능함을 판정한다.어려움9수학조합론+2아직 제출이 없습니다6초512 MB지문만 제공
Medium Hadron ColliderN-1번의 일관된 게이트 작동 뒤 1번부터 128번 구간의 빔 전하를 알아내야 한다. 129번부터 512번 구간에서 최대 10번 측정할 수 있고, 검출기는 7자리를 넘으면 값을 감싼다.어려움9수학정수론+2아직 제출이 없습니다4초512 MB지문만 제공
기저 변환계수 a_i가 주는 선형 점화식을 만족하는 모든 수열이 함께 만족하는, 지정된 지연 b_i를 갖는 유일한 점화식의 계수를 구한다.어려움9수학구현+2아직 제출이 없습니다2초512 MB채점 가능
Incomparable Pairs문자열 s의 부분 문자열 쌍 중에서 어느 쪽도 다른 쪽을 포함하지 않는 쌍의 개수를 센다.어려움9문자열정렬+2아직 제출이 없습니다3초512 MB지문만 제공
Employees수용 인원이 k인 홀과 한 명만 작업하는 방에서 이루어지는 과정을 두 가지 방식으로 평가한 점수를 모든 순열에 대해 합산하고, 직원별로 두 점수를 곱해 10^9+7로 나눈 값을 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB지문만 제공
모듈로 마방진각 행, 각 열, 두 대각선의 합이 모두 같은 상수와 합동이 되는 Z_m 위의 n x n 행렬의 개수를 n과 m이 10^9까지일 때 센다.어려움9수학조합론+2아직 제출이 없습니다1초512 MB채점 가능
Count the Sequences0 ≤ x_i ≤ b^i - c이고 합이 n보다 작은 정수 수열 x_1, ..., x_m의 개수를 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
Innocence길이 N인 배열의 각 원소가 [L, R] 범위에 있고 전체 XOR이 K가 되는 경우의 수를 여러 K에 대해 1e9+7로 나눈 나머지로 구한다.어려움9수학동적 계획법+2아직 제출이 없습니다1초512 MB지문만 제공
만화경마름모 육십면체의 60개 면을 n가지 색으로 칠하되 각 색 i를 최소 c_i번 사용하고, 회전 대칭으로 같은 색칠은 동일하게 볼 때 경우의 수를 p로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다2초512 MB채점 가능
Lost In The Echon개의 서로 다른 변수에 사칙연산과 괄호를 써서 만들 수 있는 유리식의 개수를, 유리함수로서 같은 것을 하나로 세어 1e9+7로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다8초512 MB지문만 제공
기댓값 비용n개 정점의 레이블 트리를 균일하게 무작위로 고를 때, 한 정점에서 다른 모든 정점까지 거리 합의 최솟값에 대한 기댓값을 소수 모듈로로 구한다.어려움9조합론트리+2아직 제출이 없습니다3초512 MB채점 가능
Jimp Numbers등차수열을 이루는 양의 정수 (a, b, c)에 대해 a^2 + b^2 + k = c^2을 만족하는 삼중항이 정확히 하나 존재하는 k의 개수를 n 이하에서 센다.어려움9정수론수학+2아직 제출이 없습니다2초512 MB지문만 제공
Faraway최대 10개의 조건 각각에 대해 (|xi - xe| + |yi - ye|) mod ki = ti를 만족하는 격자점 (xe, ye)가 [0, m]^2 안에 몇 개인지 세는 문제다. ki는 5 이하이고 m은 1e9까지 커질 수 있다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
Minimum Spanning Trees각 정점 쌍이 독립적으로 간선이 없거나 1부터 k까지의 가중치를 확률적으로 가질 때, 그래프가 연결되어 있고 최소 신장 트리의 가중치가 주어진 s가 될 확률을 모든 s에 대해 구한다.어려움9조합론그래프+2아직 제출이 없습니다4초512 MB지문만 제공
Line Graphs단순 무방향 그래프 G와 1 이상 4 이하의 k가 주어질 때, k번 반복한 선 그래프 L^k(G)의 최대 클리크 크기와 최대 클리크의 개수를 10억 7로 나눈 나머지를 구한다.어려움9그래프조합론+2아직 제출이 없습니다5초512 MB지문만 제공
소수 전개무한곱 (9/10)(99/100)(999/1000)...의 값을 소수로 나타냈을 때 n번째 자리 숫자를 n이 10^18까지인 각 질의마다 구한다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
Bulbasaur층마다 k개의 구멍이 있는 방향 그래프에서 모든 층 쌍에 대해 서로 정점과 간선을 겹치지 않게 보낼 수 있는 최대 덩굴 수의 합을 구한다.어려움9그래프동적 계획법+2아직 제출이 없습니다6초512 MB지문만 제공
Eevee여러 순열을 교차 병합해 같은 돌이 k개 연속으로 나오지 않게 만드는 경우의 수를 모든 연속한 스택 구간에 대해 합해 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다5초512 MB지문만 제공
Lati@sn x n 행렬에서 모든 순열 대각선으로 튜플을 만들어, 더 작은 튜플로 쪼개는 무편향 게임의 승자를 판정한다.어려움9게임 이론조합론+2아직 제출이 없습니다2초512 MB지문만 제공
The One Polynomial Man소수 p와 두 집합 S, V가 주어질 때, V에 대한 유리식의 곱이 0이 되는 S의 원소 쌍 (a,b)의 개수를 센다.어려움9수학정수론+2아직 제출이 없습니다4초512 MB지문만 제공
그래프 세기N개 노드의 연결된 무방향 라벨 그래프 중 다리가 정확히 K개인 것의 개수를 합성수일 수 있는 M으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Flip각 팀 인원이 n명으로 제한된 동전 던지기 배정 과정에서, 주어진 사람 집합이 모두 같은 팀이 될 확률을 998244353으로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다10초512 MB지문만 제공
Ineq정수 격자점들의 유한집합 S가 주어질 때, 어떤 유한개의 반평면 모두의 아래쪽에 놓이는 정수점 전체가 정확히 S가 되도록 만들 수 있는지 판정한다.어려움9기하수학+2아직 제출이 없습니다2초512 MB채점 가능
Fast as Ryser정점이 최대 36개인 무방향 그래프에서 서로 변을 공유하지 않는 변 집합 S에 대해 c^|S|의 합을 1e9+7로 나눈 나머지를 구한다.어려움9동적 계획법비트 연산+2아직 제출이 없습니다4초512 MB지문만 제공
Junk Problem서로 다른 두 원소의 XOR 값이 모두 다르게 되는 {1,...,n}의 부분집합 S를 크기 floor(sqrt(0.5n)) 이상으로 구성한다.어려움9수학조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Help Yourself (Platinum)N개의 구간으로 이루어진 모든 부분집합에 대해 합집합의 연결 성분 개수를 K제곱한 값의 합을 1e9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
스프링클러 2: 알팔파의 귀환일부 칸이 막힌 N x N 격자에 옥수수 sprinkler와 alfalfa sprinkler를 놓아 모든 칸이 정확히 한 종류의 sprinkler로만 덮이도록 하는 경우의 수를 센다.어려움9동적 계획법누적 합+2아직 제출이 없습니다2초512 MB채점 가능
소의 체조N과 소수 M이 주어질 때, 모든 N!개 순열에 대해 각 순열의 위수(항등원이 될 때까지 반복한 횟수)를 곱한 값을 M으로 나눈 나머지를 구한다.어려움9조합론정수론+2아직 제출이 없습니다2초512 MB채점 가능
Circus트리 위에 K마리의 소를 서로 다른 정점에 배치할 때, 빈 인접 정점으로 소를 옮겨 서로 도달할 수 있는 배치들을 같은 부류로 묶는다. 각 K마다 배치 부류의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9트리DFS+2아직 제출이 없습니다1초512 MB지문만 제공
소의 아침 운동N과 소수 M이 주어질 때, 길이 N인 순열의 위수가 K가 되는 모든 양의 정수 K의 합을 M으로 나눈 나머지를 구한다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
남현욱길이 n인 순열 중 길이 3인 증가 부분 수열이 정확히 m개인 것들의 반전 수 합을 998,244,353으로 나눈 나머지를 구한다. 단, 0 ≤ m ≤ 3이다.어려움9조합론동적 계획법+1아직 제출이 없습니다2초1024 MB지문만 제공
레이저 증폭아래 왼쪽에서 들어온 광자 하나가 w x h 격자에서 n개의 확정 결함 칸을 제외한 나머지 칸이 확률 1-p로 결함일 때 오른쪽 위에서 기대값 k개의 광자를 내도록 하는 p를 구하고, 불가능하면 -1을 출력한다.어려움9수학조합론+2아직 제출이 없습니다2초64 MB채점 가능
피보나치 수의 최대공약수의 합처럼 보이지만... ×251 이상 n 이하의 모든 i, j에 대해 gcd(i,j)^k 곱하기 gcd(F_i, F_j)의 합을 1,000,000,007로 나눈 나머지를 구한다.어려움9수학정수론+2아직 제출이 없습니다2초256 MB지문만 제공
Embeddings길이 10^6 이하의 문자열에서 서로 엄격히 포함되는 회문 부분문자열의 중첩 수열 개수를 998244353으로 나눈 나머지를 구한다.어려움9문자열동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Fox Labeling무작위로 라벨을 찍는 과정을 반복해 n마리의 여우가 모두 서로 구별될 때까지 걸리는 기대 시간을 분 단위로 구한다.어려움9확률동적 계획법+1아직 제출이 없습니다3초512 MB지문만 제공
Empodia에 관한 또 다른 문제길이 i인 순열을 framed interval(최댓값과 최솟값의 차가 구간 길이에서 1을 뺀 값인 구간) 관계로 묶었을 때의 동치류 개수를 각 i마다 소수 P로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
신기한 공놀이각 질의 (N, M)마다 두 공을 꺼낼 때 적어도 하나가 빨간색이 아닐 확률이 정확히 1/N²이 되는 M번째로 작은 주머니 크기 A를 찾아 A와 B를 10⁹+7로 나눈 나머지로 출력한다.어려움9정수론수학+2아직 제출이 없습니다0.5초256 MB채점 가능
트리 평균 가중치일부 차수가 자유로운 차수 수열이 주어질 때, 레이블 트리를 균등하게 무작위로 골라 가중치 u*sz(u)+v*sz(v)의 기댓값의 정수 부분을 구한다.어려움9조합론트리+2아직 제출이 없습니다1초256 MB채점 가능
수열 이어가기n개의 값이 주어질 때, 998244353을 법으로 가능한 한 낮은 차수의 다항식과 일치하도록 수열을 m개 더 연장한다.어려움9수학정수론+2아직 제출이 없습니다4초256 MB채점 가능
Alice and Bob (and string): Double Menace문자열 s가 주어질 때, t에서 시작하는 위치 확장 게임이 선수 승리가 되는 부분 문자열 중 k번째로 사전순으로 작은 것을 구한다.어려움9문자열게임 이론+2아직 제출이 없습니다2초512 MB지문만 제공
서로 다른 합mand 개수 세기양의 정수 n을 m개의 양의 정수 합으로 나타내는 모든 순서 있는 분할에 대해, 서로 다른 값의 개수 f를 모두 더한 값을 998244353으로 나눈 나머지를 구한다. n은 1e18까지, m은 500까지 주어진다.어려움9조합론수학+2아직 제출이 없습니다2초256 MB채점 가능
Gnutella Chessmastern x n 체스판에 k개의 비숍을 서로 공격하지 않게 놓는 경우의 수를 k = 1부터 2n-1까지 각각 998244353으로 나눈 나머지로 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다3초512 MB지문만 제공
Maximum Weighted Matching에지를 복사하고 세분화하는 과정으로 만들어진 그래프에서 최대 가중 매칭의 가중치 합과 그러한 최대 매칭의 개수를 10^9+7로 나눈 나머지를 구한다.어려움9동적 계획법트리+2아직 제출이 없습니다4초256 MB지문만 제공
Chiaki 수열 다시 보기자기 참조 수열 a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}}의 처음 n개 항의 합을 10^9+7로 나눈 나머지를 구한다.어려움9수학조합론+2아직 제출이 없습니다1초256 MB채점 가능
RMQ 유사 수열수열 A가 주어질 때, 모든 부분 구간에서 A와 같은 RMQ 결과를 내는 [0,1] 구간의 무작위 실수 수열 B의 기댓값 합을 1e9+7로 나눈 나머지를 구한다.어려움9트리조합론+2아직 제출이 없습니다2초256 MB채점 가능
Rikka와 진분수분모가 n 이하인 기약 진분수 e/f 가운데 주어진 두 분수 a/b 와 c/d 사이에 있는 것의 개수를 998244353으로 나눈 나머지로 구한다.어려움9정수론수학+2아직 제출이 없습니다10초512 MB채점 가능
Rikka with Bridgesi와 j 사이에 간선이 없고 둘 모두 k와 인접한 경우 (i,j,k)를 브리지라 할 때, 브리지가 K개 이하인 n개 정점의 무방향 그래프 개수를 m으로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB지문만 제공
Good Gamen차원에서 원점부터 목표점까지 좌표가 비감소하는 경로 중 m개의 장애물을 지나지 않는 경로의 수를 10^9+7로 나눈 나머지를 구한다.어려움9조합론동적 계획법+2아직 제출이 없습니다2초512 MB채점 가능
Hamilton Path방향 그래프에서 모든 두 정점 사이에 연속한 위치를 잇는 간선만 존재하도록 하는 순열의 개수를 세고, 개수가 n 이하이면 그 값들을 사전순으로 출력한다.어려움9그래프조합론+2아직 제출이 없습니다4초512 MB지문만 제공
택시가중치가 있는 트리에 M대의 택시와 M명의 손님을 배치하는 모든 경우에 대해, 최대 비용 완전 매칭의 총 거리 합을 10^9+7로 나눈 나머지를 구한다.어려움9트리동적 계획법+2아직 제출이 없습니다1.5초256 MB채점 가능
사탕각 질의 k마다, 가장 좋아하는 사탕 한 종류만 사서 정확히 k달러가 남는 (아이, 사탕 종류) 쌍의 개수를 2로 나눈 나머지를 구한다.어려움9정수론수학+2아직 제출이 없습니다1초512 MB채점 가능
Nice Numbers어떤 진법 d에서 자릿수가 0부터 d-1의 순열이 되는 수를 [L, R] 범위에서 세어 998244353으로 나눈 나머지를 구한다. L과 R은 최대 5000자리 정수이다.어려움9조합론정수론+2아직 제출이 없습니다1초512 MB채점 가능
From The Insiden x m 판에서 빈 k x k 정사각형을 번갈아 칠하고 둘 곳이 없는 사람이 지는 게임에서, 앨리스가 이기게 되는 첫 수의 개수를 센다.어려움9게임 이론조합론+2아직 제출이 없습니다1초512 MB지문만 제공
Vertex covers정점이 n개인 단순 그래프 가운데 최소 정점 덮개의 크기가 정확히 k인 그래프의 개수를 2로 나눈 나머지를 구한다.어려움9조합론수학+2아직 제출이 없습니다3초512 MB지문만 제공
배열 챌린지선형 점화식 h와 닫힌 형태의 배열 b, a가 주어질 때 n이 10^15까지 커질 수 있는 floor(sqrt(a_n))을 10^9+7로 나눈 나머지를 구한다.어려움9수학정수론+2아직 제출이 없습니다1초512 MB채점 가능
주 선생과 사탕사탕 더미 n개가 주어지고, 각 차례에 한 더미에서 양의 개수를 덜어내거나 한 더미를 비어 있지 않은 세 더미로 나눌 수 있을 때 최적 플레이에서 승자를 판정한다.어려움9게임 이론수학+2아직 제출이 없습니다3초512 MB채점 가능
주 사부와 도약자최대 100개의 장애물이 있는 거대한 격자에서 (1,1)에서 (n,m)까지 도약 말로 이동하는 단조 경로의 수를 110119로 나눈 나머지를 구한다.어려움9동적 계획법조합론+2아직 제출이 없습니다1초512 MB채점 가능
무작위 점일반 위치에 있는 n개의 점이 주어질 때, 무작위로 고른 부분집합의 볼록 껍질 꼭짓점 수 기댓값에 2^n을 곱한 값을 1e9+7로 나눈 나머지를 구한다.어려움9기하조합론+2아직 제출이 없습니다5초512 MB채점 가능
GCD vs LCMn, m, a가 1e5 이하인 q개의 질의마다 i<=n, j<=m이고 gcd(i,j)<=a인 모든 쌍의 lcm(i,j) 합을 1e9+7로 나눈 나머지를 구한다.어려움9정수론수학+2아직 제출이 없습니다2.5초512 MB채점 가능
Subspace원소가 q개인 유한체 위 n차원 벡터 공간의 k차원 부분공간 개수를 소수 p로 나눈 나머지를 구한다. q와 n은 최대 10억이다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB지문만 제공
XOR의 거듭제곱n개의 정수가 주어질 때, 모든 2^n개 부분집합에 대해 부분집합 원소들의 XOR의 popcount의 k제곱을 합한 값을 1e9+7로 나눈 나머지를 구한다.어려움9비트 연산수학+2아직 제출이 없습니다6초512 MB채점 가능
Harary정점 N개짜리 유향 그래프 중 위상 정렬이 정확히 1개, 2개, 3개인 그래프의 개수를 각각 1e9+7로 나눈 나머지로 구한다.어려움9조합론수학+2아직 제출이 없습니다1초512 MB지문만 제공