問題一覧 > 通常問題

No.1810 RGB Biscuits

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 : MasKoaTSMasKoaTS / テスター : polylogKpolylogK 👑 ygussanyygussany
2 ProblemId : 7014 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 20:48:16

追記(2022/04/25)

yukicoderの数式表示がMathJaxからKaTeXへ移行したことに伴い、問題文・解説の更新を行いました。

何か不備等ありましたら、作問者の方までご一報いただけると幸いです。

問題文

ある不思議なポケットに赤色ビスケットと緑色ビスケットが $1$ 個ずつ入っています。

好奇心旺盛なコアさんは、このポケットを $T$ 回叩くことにしました。
ポケットを $t$ $(1 \leq t \leq T)$ 回目に叩いたとき、ビスケットの色と数が次のように変化します。

  • $t$ が奇数のとき、赤色ビスケット $1$ 個につき $A$ 個、緑色ビスケット $1$ 個につき $B$ 個の青色ビスケットが、
    新たにポケット内に追加される。

  • $t$ が偶数のとき、緑色ビスケットがすべて消滅した後、赤色ビスケットがすべて緑色ビスケットに変化し、
    その後、青色ビスケットがすべて赤色ビスケットに変化する。

$N$ 個の整数値 $T_{1},T_{2}, \dots ,T_{N}$ が与えられます。

各 $i$ $(1 \leq i \leq N)$ ごとに、$T_{i}$ 回叩いた後のポケット内に存在するビスケットの総数を
$10^{9}+7$ で割った余りを求めてください。

制約

  • $1 \leq A,B \leq 10^{9}$

  • $1 \leq N \leq 1000$

  • $0 \leq T_{i} \leq 10^{18}$ $(1 \leq i \leq N)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$A$ $B$
$N$
$T_{1}$
$T_{2}$
 $\vdots$
$T_{N}$
  • $1$ 行目には $A$ と $B$ がこの順に空白区切りで与えられる

  • $2$ 行目には $N$ が与えられる

  • $(2+i)$ $(1 \leq i \leq N)$ 行目には $T_{i}$ が与えられる

出力

答えを $1$ 行ずつ合計 $N$ 行に出力し、最後に改行してください。

$i$ $(1 \leq i \leq N)$ 行目には、$T_{i}$ 回叩いた後のポケット内に存在するビスケットの総数を
$10^{9}+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
3 2
5
0
1
2
3
4
出力
2
7
6
23
22

ビスケットの色と数の変化は下の表のようになります。

  色 / 回数 t     0     1     2       3       4  
    赤   1     1     5       5     17  
    緑   1     1     1       1       5  
    青   0     5     0     17       0  
    合計   2     7     6     23     22  

サンプル2
入力
1 2
10
3
50
327362983
5271559
19
8467387694249466
10704815128332
2578440
758998
5041
出力
9
67108864
331052732
465750649
2389
265767032
562491267
423879848
257896762
389805843

ポケット内に存在するビスケットの総数を $10^{9}+7$ で割った余りを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。