No.980 Fibonacci Convolution Hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 60
作問者 : keymoonkeymoon / テスター : tempura_pptempura_pp
9 ProblemId : 3211 / 出題時の順位表
問題文最終更新日: 2020-01-30 13:53:58

問題文

数列 $a$ を $a_1=0, a_2=1,a_{n}=p \cdot a_{n-1} + a_{n-2}(3 \leq n)$ で定義します。また、$Q$ 個のクエリが与えられます。
各クエリ $q_i$ について、以下の問題に回答してください。

  • $s+t=q_i, 1 \leq s,t$ なる全ての整数 $s,t$ について、$a_s \cdot a_t$ の合計を $1000000007$ で割った余りを答えてください。

入力

$p\\Q\\q_1\\\vdots\\q_Q$
  • $1 \leq p \leq 10^9$
  • $1 \leq Q \leq 2\cdot 10^5$
  • $2 \leq q_i \leq 2\cdot 10^6$
  • 入力は全て整数

出力

$Q$ 行出力して下さい。$i$ 行目には、$s+t=q_i, 1 \leq s,t$ なる全ての整数 $s,t$ について、$a_s \cdot a_t$ の合計を $1000000007$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
3
4
5
6
出力
1
6
29

数列 $a$ は $0\ 1\ 3\ 10\ 33\ 109\cdots$ と続きます。
クエリ1で求めるべき答えは $a_1 \cdot a_3 + a_2 \cdot a_2 + a_3 \cdot a_1$ なので、$0 + 1 + 0 = 1$ 、
クエリ2で求めるべき答えは $a_1 \cdot a_4 + a_2 \cdot a_3 + a_3 \cdot a_2 + a_4 \cdot a_1$ なので、$0 + 3 + 3 + 0 = 6$ 、
クエリ3で求めるべき答えは $a_1 \cdot a_5 + a_2 \cdot a_4 + a_3 \cdot a_3 + a_4 \cdot a_2 + a_5 \cdot a_1$ なので、$0 + 10 + 9 + 10 + 0 = 29$ となります。

サンプル2
入力
3141592
6
535
8979
3238
4626
4338
3279
出力
249873862
219934200
58952263
243315871
417706621
611158423

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