#161. 乘法逆元 2

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

这可能是一道模板题。

给定 n 个正整数 a_i ,求每个数在模 p 意义下的乘法逆元。

提示:请使用高效的读入方式。

输入格式

第一行一个整数 n

第二行 n 个整数 a_i

输出格式

一行一个数,表示 \sum_{i=1}^n a_i^{-1} \times 998244353^{n-i} \pmod p

样例

样例输入

5
4
7
8
12
123456

样例输出

650798912

样例解释

五个数的逆元分别是:

250000002
142857144
125000001
83333334
78351802

数据范围与提示

对于 100\% 的数据,有 1 \le n \le 5000000 , 1 \le a_i < p , p=10^9+7

由于本题对常数有一定要求,故不建议 C/C++ 选手选择 C++ (NOI)C++11 (NOI) 编译器。

2019.8.20 新加数据一组