XOR Problem III
Xem PDF
Điểm:
1800
Thời gian:
1.0s
Bộ nhớ:
32M
Input:
bàn phím
Output:
màn hình
Cho số nguyên \(N\).
Đặt
\[
F(x)=\prod_{i=1}^{N}(1+a_i x)
\]
với mọi \(a_i\) là các số nguyên modulo \(998244353\).
Bạn không biết dãy \(a_i\).
Thay vào đó, bạn được cho \(N\) hệ số đầu tiên của
\[
G(x)=\ln F(x).
\]
Cụ thể,
\[
G(x)=\sum_{i=1}^{N} g_i x^i+O(x^{N+1}).
\]
Hãy tính
\[
\sum_{i=1}^{N} a_i
\]
lấy modulo \(998244353\).
Đảm bảo luôn tồn tại duy nhất một đa thức \(F(x)\) thỏa mãn:
- \(F(0)=1\).
- \(\deg(F)\le N\).
- \(\ln(F(x))\equiv G(x)\pmod{x^{N+1}}\).
Input
- Dòng đầu chứa số nguyên \(N\) (\(1\le N\le2\times10^5\)).
- Dòng thứ hai chứa \(N\) số nguyên \(g_1,g_2,\ldots,g_N\) modulo \(998244353\).
Output
In ra
\[
\left(\sum_{i=1}^{N}a_i\right)\bmod998244353.
\]
Example
Test
Input
3
6 499122159 72Output
12
Bình luận