Eau de Cologne

링크: https://yukicoder.me/problems/no/137 문제 요약: $A_1$원, $A_2$원, $\cdots$, $A_N$원짜리 동전이 있습니다. 이 동전을 적당히 사용해서 합이 $M$원이 되도록 만드는 되는 경우의 수를 $1\,234\,567\,891$로 나눈 나머지를 구하세요. 하나 이상의 동전의 개수가 다른 경우 다른 경우로 셉니다. 제한 시간 제한: 5초 / 메모리 제한: 512MB $1 \le N \le 50$ $1 \le M \le 10^{18}$ $1 \le A_1 < A_2 < \cdots < A_N \le 500$ 풀이 더보기 $\sum c_NA_N = M$이 되는 $0$ 이상의 수로 이루어진 $(c_1, \cdots, c_N)$ 순서쌍의 개수를 세는 문제입니다. $..

No. 1873 Bracket Swapping 문제 링크 제한 시간 제한: 2초 메모리 제한: 512MB 문제 올바른 괄호 문자열 $S$와 음이 아닌 정수 $K$가 주어집니다. $S$에 대해 다음 조작을 $K$번 반복한 이후의 $S$가 올바른 괄호 문자열이 되는 경우의 수를 $998244353$으로 나눈 나머지를 구해주세요. $1 \le i < j \le |S|$를 만족하는 정수 $(i, j)$를 고른다. $S$의 $i$번째 문자와 $j$번째 문자를 교환한다. 단, 어떤 정수 $l$ ($1 \le l \le K)$가 존재해서 $l$번째 고른 $(i, j)$가 다른 경우, 또한 그 경우에 한해서 두 조작방법을 다르다고 합니다. 올바른 괄호 문자열의 정의 다음을 만족하는 괄호 문자열을 올바른 괄호 문자열이라..

問題: https://yukicoder.me/problems/no/1857 $X$が正の整数の時、$E[X] = P(X \ge 1) + P(X \ge 2) + P(X \ge 3) + \cdots$あ成立します。 $P(X \ge k)$のためには、最初の$k-1$回引いた品物が全部違う必要があります。 最初の$k-1$回で決めた順番に品物を引く確率は簡単にそれぞれの積に計算できます。 最初の$k-1$回で順番を決める方法は$k-1$個の品物を決めたあと順番を決めるのでできます。 $P(X \ge k) = (k-1)!\times\sum_{S \subset \{1, \cdots, n\}, |S| = k-1} \left(\prod_{i \in S} p_i\right)$になります。 $\prod_{1 \le i \le N} (1+p_ix)$の$..

Yukicoder No. 119 여행 문제 문제 링크 문제 $N$ 개의 나라가 있습니다. 나라는 $0$번부터 $N-1$번까지 번호가 붙어있습니다. A군은 $N$개의 나라 중 방문하고 싶은 나라를 골랐습니다. A군은 반드시 번호가 작은 나라부터 차례로 방문을 합니다. 여행사에는 각 나라별로 $1$개씩의 여행 패키지가 있습니다. 여행 패키지에 참여하는 게 좋을 때도 있지만 자유도가 줄어들어서 싫을 때도 있습니다. 여행 패키지에 참여할 때와, 참여하지 않을 때의 만족도가 정해져 있습니다. 또한, 여행사 직원의 말은, "한 나라의 여행 패키지에 참여하면, 다른 나라의 여행 패키지에도 참여해야 한다." 같은 조건이 있는 경우도 있다고 합니다. 예를 들면, $x$번 나라의 여행 패키지에 참여하면, $y$번 나라의 ..

Yukicoder No. 114 먼 미래 문제 링크 문제 SRM 10000이 열린 것도 옛날이야기. 여기서는 대회의 Div2 Easy 문제를 소개하려고 한다. 문제 간단히 말하면, 방향이 없고 가중치가 붙어있는 그래프가 주어진다. 정점 중 몇 개는 "중요"한 점이다. 모든 중요한 점을 연결하는 부분 그래프 중 간선 가중치 합이 최소가 되는 것을 구하고 싶다(이 그래프는 트리이다). 그때의 가중치 합을 출력하는 문제. 입력 자세한 입력 형식은, 원문을 확인해주세요. 입력의 1번째 줄에는 정점 수 $N$, 간선 수 $M$, 중요한 정점 수 $T$가 주어지고, 다음 $M$ 개의 줄에 $3$개의 정수 $a_i$, $b_i$, $c_i$가 정점 $a_i$와 정점 $b_i$를 가중치 $c_i$로 잇는다는 의미로 주..

Yukicoder No. 95 Alice and Graph 문제 링크 문제 Alice는 생일 선물로 방향성이 없는 그래프를 받았습니다. 그리고 평소처럼 그래프를 가지고 게임을 합니다. 그래프는 $N$ 개의 정점이 있고, $1$번부터 $N$번까지 번호가 붙어있으며, $k$번 정점에는 $2^{k-1}-1$ 개의 동전이 있습니다. 게임을 시작할 때, Alice는 $1$번 정점에 있습니다. $2^{1-1}-1=0$이기 때문에, $1$번 정점에는 동전이 없습니다. 그리고 Alice는 최대 $K$번 이동할 수 있습니다. 각 이동에서, Alice는 간선을 따라 인접한 정점으로 이동할 수 있고, 정점에 있는 동전을 수집할 수 있습니다. (주: 같은 정점을 두 번 방문하는 경우에도, 동전은 한 번만 수집할 수 있습니다...