No.980 Fibonacci Convolution Hard
タグ : / 解いたユーザー数 95
作問者 :
keymoon
/ テスター :
tempura_pp
問題文
数列 $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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。