#P6935. 我永远喜欢

    ID: 6766 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-双射计数容斥原理第二类 Stirling 数普通生成函数卷积转化NTT分治乘积阶乘逆元预处理

我永远喜欢

题目描述

有 nn 类樱花,第 ii 类有 cic_i 朵。同类樱花不可区分。考虑将全部樱花排成序列的每一种不同结果。

对一个序列,把首尾相接以确定相邻关系,然后按类别划分成极长连续段。同一段内的樱花类别相同,相邻两段的类别不同。若一段的长度为 ℓ\ell,它对快乐值的贡献为 1/ℓ!1/\ell!。该序列的快乐值等于所有段的贡献之积。

求所有不同序列的快乐值之和对 998244353998244353 取模的结果。不同序列仍分别计入,即使它们首尾相接后可以通过旋转互相得到。模意义下的除法使用乘法逆元。

输入格式

第一行一个整数 nn。

第二行 nn 个正整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

输出一行一个整数,表示所求的快乐值总和对 998244353998244353 取模的结果。

样例

2
2 2
3

共有 66 种序列。1122,1221,2211,21121122,1221,2211,2112 的快乐值均为 1/41/4,1212,21211212,2121 的快乐值均为 11,总和为 33。

6
7 8 9 10 11 12
526836707

数据范围

本站评测中,1<n≤∑ci≤2000001<n\le\sum c_i\le200000,且 ci≥1c_i\ge1。原 PDF 中给出的类别数上限为 100000100000。原题时间限制 3 秒,内存限制 512 MB。

子任务 分值 附加限制
1 15 ∑ci≤10\sum c_i\le10
2 n≤100n\le100,ci≤100c_i\le100
3 20 n≤500n\le500,ci≤500c_i\le500
4 n=2n=2
5 30 无

原 PDF 题面