쌍둥이 계단 수열
골드 II의견: 0
두 수열 \(A\)와 \(B\)가 다음과 같이 정의된다.
$$ A(0) = a_0, \quad B(0) = b_0 $$
$$ A(n) = x \cdot A(n-1) + y \cdot B(n-1) \quad (n \ge 1) $$
$$ B(n) = z \cdot A(n-1) + w \cdot B(n-1) \quad (n \ge 1) $$
모든 계산은 \(10^9 + 7\)로 나눈 나머지를 사용한다.
\(Q\)개의 쿼리가 주어진다. 각 쿼리 \((l, r)\)에 대해
$$ \sum_{k=l}^{r} A(k) \bmod (10^9+7) $$
을 출력하여라.
- \(0 \le a_0, b_0, x, y, z, w < 10^9+7\)
- \(1 \le Q \le 20\)
- \(0 \le l \le r \le 10^{18}\)
첫째 줄에 \(a_0\), \(b_0\)이 공백으로 구분되어 주어진다.
둘째 줄에 \(x, y, z, w\)가 공백으로 구분되어 주어진다.
셋째 줄에 \(10^9 + 7\)이 주어진다 (항상 이 값이다).
넷째 줄에 쿼리 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 쿼리 \(l\), \(r\)이 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 쿼리의 답을 순서대로 출력한다.
1 1
1 1 1 1
1000000007
2
1 3
0 4
14
31
\(A\)와 \(B\) 모두 두 배씩 증가한다. \(A(0..4)=1,2,4,8,16\)이고, 구간 \([1,3]\)의 합은 \(14\), \([0,4]\)의 합은 \(31\)이다.
1 1
2 0 0 3
1000000007
1
0 3
15
\(A(n)=2^n\)이므로 \(A(0)+A(1)+A(2)+A(3)=1+2+4+8=15\)이다.
riseoj 작성
출처 Original
평가 및 의견
쌍둥이 계단 수열
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
쌍둥이 계단 수열