a341. TOI 2020/05 潛力組：總和

題目描述

數列的前兩項為 x1=x2=1。對每個 n≥3，定義 xn=a×x(n−1)+b×x(n−2)。給定 a、b 與下標區間 lb、ub，請求出從 xlb 加到 xub 的總和，包含兩端。答案可能很大，僅需回報除以 10^9+9 的餘數。

輸入格式

輸入只有一行，依序為四個正整數 a、b、lb、ub，以空白分隔。

• 1 ≤ a、b ≤ 10^9
• 4 ≤ lb ≤ ub ≤ 10^9

分組：10 分滿足 ub−lb≤10^2、ub≤10^3、a=b=1；20 分滿足 ub−lb≤10^2、ub≤10^3；40 分滿足 ub−lb≤10^5；30 分無額外限制。

輸出格式

輸出一個整數，為 xlb+x(lb+1)+…+xub 除以 1000000009 的餘數。

範例 1

輸入：

1 1 5 5

輸出：

5

範例 2

輸入：

12 34 56 78

輸出：

37811150

範例 3

輸入：

2020 108 8888 99999

輸出：

289363613

範例 4

輸入：

888888 111111 99999 777777777

輸出：

405098263

來源

TOI 2020/05 練習賽潛力組〈總和〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202005/Sum.pdf