No.980 Fibonacci Convolution Hard
タグ : / 解いたユーザー数 100
作問者 :
keymoon
/ テスター :
tempura_pp
Problem Statement
Define a sequence $a$ by $a_1=0, a_2=1,a_{n}=p \cdot a_{n-1} + a_{n-2}(3 \leq n)$. You are also given $Q$ queries.
For each query $q_i$, answer the following problem.
- Find the sum of $a_s \cdot a_t$ over all integers $s,t$ such that $s+t=q_i, 1 \leq s,t$, modulo $1000000007$.
Input
$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$
- All inputs are integers.
Output
Output $Q$ lines. On the $i$-th line, output the sum of $a_s \cdot a_t$ over all integers $s,t$ such that $s+t=q_i, 1 \leq s,t$, modulo $1000000007$.
Sample
Sample 1
Input
3
3
4
5
6
Output
1
6
29
The sequence $a$ continues as $0\ 1\ 3\ 10\ 33\ 109\cdots$.
The answer to query 1 is $a_1 \cdot a_3 + a_2 \cdot a_2 + a_3 \cdot a_1$, so it is $0 + 1 + 0 = 1$;
the answer to query 2 is $a_1 \cdot a_4 + a_2 \cdot a_3 + a_3 \cdot a_2 + a_4 \cdot a_1$, so it is $0 + 3 + 3 + 0 = 6$;
the answer to query 3 is $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$, so it is $0 + 10 + 9 + 10 + 0 = 29$.
Sample 2
Input
3141592
6
535
8979
3238
4626
4338
3279
Output
249873862
219934200
58952263
243315871
417706621
611158423
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。