A6000. 小 Q 的序列
编程题
省选/NOI-
知识点
题目描述
小 Q 喜欢在序列上数数。
定义一个序列 $a_{1\ldots k}$ 的权值为 $\prod_{i = 1}^k(a_i + i)$。
现在小 Q 有一个长度为 $n$ 的序列 $c_{1\ldots n}$。
他想知道他的序列的所有 $2^n - 1$ 个非空子序列的权值和。
由于答案很大，你只需要输出答案对 $998244353$ 取模的结果。
定义一个序列 $a_{1\ldots k}$ 的权值为 $\prod_{i = 1}^k(a_i + i)$。
现在小 Q 有一个长度为 $n$ 的序列 $c_{1\ldots n}$。
他想知道他的序列的所有 $2^n - 1$ 个非空子序列的权值和。
由于答案很大，你只需要输出答案对 $998244353$ 取模的结果。
输入格式
第一行，一个正整数 $n$。
接下来一行，$n$ 个非负整数，代表长度为 $n$ 的序列 $c_{1\ldots n}$。
接下来一行，$n$ 个非负整数，代表长度为 $n$ 的序列 $c_{1\ldots n}$。
输出格式
一行，一个非负整数，答案对 $998244353$ 取模的结果。
输入输出样例
输入 #1
3 1 2 3
输出 #1
90
说明/提示
对于 $25\%$ 的分数，$1 \leq n \leq 1000$；
对于另外 $25\%$ 的分数，$c_i (1 \leq i \leq n)$ 为等差数列且公差为 $\pm 1$；
对于所有数据：$1 \leq n \leq 100000$，对于 $1\leq i \leq n$，有 $0 \leq c_i \leq 998244352$。
对于另外 $25\%$ 的分数，$c_i (1 \leq i \leq n)$ 为等差数列且公差为 $\pm 1$；
对于所有数据：$1 \leq n \leq 100000$，对于 $1\leq i \leq n$，有 $0 \leq c_i \leq 998244352$。