UOJ Logo Zijian Online Judge

ZOJ

#47. 梦中的项链

Statistics

现在有若干种宝石,其中有 $a_k$ 种重量为 $k$。你想知道对于每个 $w\le n$,有多少种宝石串成的项链,使得项链上至少有 $2$ 个宝石,且相邻的宝石均属于不同种类,且这串宝石的总重量为 $w$。答案对 $998244353$ 取模。

注意:

  • 项链的第一个宝石与最后一个宝石也应属不同种类。
  • 如果两个方案可以通过旋转或翻转变成一致,也应当被认为是不同的方案。

输入格式

第一行输入一个正整数 $n$。

接下来输入一行 $n$ 个数,第 $k$ 个数表示 $a_k$。

输出格式

输出一行 $n + 1$ 个数,分别表示 $w=0,1,\dots n$ 时的方案数。

样例一

input

5
2 1 0 1 0

output

0 0 2 4 8 12

explanation

以下的乘号可认为是旋转生成:

$$ 2:[1,1']\times 2\\ 3:[1,2]\times 2,[1',2] \times 2\\ 4:[1,1',1,1'] \times 2,[1,1',2]\times 3,[1',1,2]\times 3\\ 5:[1,4]\times 2, [1',4]\times 2, [1,1',1,2]\times 4, [1',1,1',2]\times 4 $$

样例二

见下发文件。

限制与约定

对于 $100\%$ 的数据,保证 $2 \le n\le 10^5, 0 \le a_i < 998244353$。

测试点编号$n$特殊限制
$1$$\le 8$
$2$$\le 50$
$3$$\le 10^5$只存在重量为 $1$ 的宝石
$4$$\le 3\times 10^2$
$5$
$6$
$7$$\le 3\times 10^3$
$8$
$9$$\le 10^5$
$10$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载