#P8863. [2023省队模拟]不是打表题

    ID: 8957 传统题 1000ms 512MiB 尝试: 13 已通过: 3 难度: 8 上传者: 标签>图论数论CF2400搜索回溯法DFS构造数学

[2023省队模拟]不是打表题

不是打表题

时间限制:1.0s 内存限制:512.0MB

问题描述

给定一正整数 nn 和长度为 nn的序列 ww,定义一个集合SS 的权值为 ∏i∈Swi\prod_{i \in S} w_i。 求 1,2,...,n1,2,...,n 的子集 SS 的权值和,其中 SS 不能包含三个互不相同的正整数 (a,b,c)(a,b,c),使得 a∣ba\mid b 且 b∣cb\mid c。答案对 998244353 取模。

数据范围:n≤120n\le 120。

输入格式

第一行包含一个正整数nn。第二行包含 nn 个非负整数 w1,w2,...,wnw_{1},w_{2},...,w_{n}。

输出格式

一行一个非负整数,表示答案。

样例 #1

输入

4
1 1 1 1

输出

14

样例 #2

输入

10
1 2 3 4 5 6 7 8 9 10

输出

10619360

补充样例 3

60
1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
22

只有编号 1,2,4,8,16,321,2,4,8,16,32 的权值为 11,其他权值为 00。对答案有贡献的集合至多选择这六个编号中的两个,因此答案为 1+6+(62)=221+6+\binom62=22。

评测用例规模与约定

对于所有数据,保证 1≤n≤120,0≤wi≤9982443521\le n\le 120,0\le w_{i}\le 998244352。

测试点 n上限
1 20
2 30
3 40
4 50
5 60
6 80
7 90
8 100
9 110
10 120