No.754 Sum of Convolution
レベル :
/ AI推定難易度 : 450
/ 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 251
作問者 :
37zigen
/ テスター :
horiesiniti
タグ : / 解いたユーザー数 251
作問者 :
37zigen
/ テスター :
horiesiniti
問題文最終更新日: 2019-09-30 16:23:35
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2018
(順位表)
の他の問題:
Problem Statement
There are functions $f(x), g(x)$. Suppose they can be expressed as $f(x)=\sum_{i=0}^{\infty} a_ix^i$ and $g(x)=\sum_{i=0}^{\infty} b_ix^i$.
You are given $a_0, a_1, ..., a_{n-1}, a_{n}$ and $b_0, b_1, ..., b_{n-1}, b_{n}$. Letting $f(x)g(x)=\sum_{i=0}^{\infty} c_ix^i$, find $\sum_{i=0}^{n} c_i$ $\mod 10^9+7$.
Input
$n$
$a_0$
$a_1$
$\vdots$
$a_{n-1}$
$a_n$
$b_0$
$b_1$
$\vdots$
$b_{n-1}$
$b_n$
$0≦n≦10^5$
$0≦a_i<10^9+7$ $(i=0,1,...,n-1,n)$
$0≦b_i<10^9+7$ $(i=0,1,...,n-1,n)$
$n,a_i,b_i$ $(i=0,1,...,n-1,n)$ are all integers.
Output
Output $\sum_{i=0}^{n} c_i\mod 10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
0 2 4
Output
8
Sample 2
Input
2 3 2 2 7 0 4
Output
61
Sample 3
Input
10 411800281 374147632 964985155 329102256 926008502 57683481 838879783 936365822 581256410 185640965 859403279 599166523 911066531 458453668 513273629 669552870 958847634 616971567 299644000 426685985 169658392 679631261
Output
386501285
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。