제한 있는 동전 채우기
다이아몬드 III의견: 0
\(K\)종류의 동전이 있다. \(i\)번째 동전의 가치는 \(v_i\)이고, 이 동전은 반드시 \(l_i\)개 이상 \(r_i\)개 이하로 사용해야 한다.
사용한 모든 동전의 가치 합이 정확히 \(S\)가 되도록 하는 방법의 수를 \(998{,}244{,}353\)으로 나눈 나머지로 구하여라. 동전은 종류별로 구분되며, 같은 종류의 동전끼리는 구분하지 않는다 (즉 각 종류를 몇 개 쓰는지만이 중요하다).
\(1 \le K \le 100{,}000\)
\(0 \le S \le 100{,}000\)
\(1 \le v_i \le 100{,}000\)
\(0 \le l_i \le r_i \le 100{,}000\)
첫 줄에 동전의 종류 수 \(K\)와 목표 합 \(S\)가 주어진다.
이어서 \(K\)개의 줄에 각각 \(v_i\), \(l_i\), \(r_i\)가 주어진다.
조건을 만족하는 방법의 수를 \(998{,}244{,}353\)으로 나눈 나머지를 한 줄에 출력한다.
2 5
1 0 3
2 1 2
2가치1 동전 0~3개, 가치2 동전 1~2개로 합 5를 만드는 방법. 가치2를 1개(2) 쓰면 가치1을 3개(3)=합5; 가치2를 2개(4)면 가치1 1개(1)=합5. 두 가지.
2 13
3 1 1
5 0 2
1가치3 동전 정확히 1개(3 고정), 가치5 동전 0~2개. 합 13이 되려면 가치5를 2개(10) 써서 3+10=13. 한 가지.
riseoj 작성
출처 Original
평가 및 의견
제한 있는 동전 채우기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
제한 있는 동전 채우기