No.980 Fibonacci Convolution Hard

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.980 Fibonacci Convolution Hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 94
作問者 :

keymoon / テスター :

tempura_pp

10 ProblemId : 3211 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-09-17 18:18:43

問題文

数列 $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}$ 
 $⋮$ 
 $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

入力

出力

1
6
29

数列 $a$ は $0 1 3 10 33 109 \dots$ と続きます。
クエリ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

入力

出力

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

yukicoder

No.980 Fibonacci Convolution Hard

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力