#P10383. [2021年联测]线性基

    ID: 9501 传统题 2000ms 512MiB 尝试: 9 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-FWT卷积转化查询排序奇偶块排序阶乘逆元预处理Pascal 递推分治算法

[2021年联测]线性基

题目描述

给定一个多重集合 SS。对于每个整数 ii(0≤i<2m0\le i<2^m),集合中有 aia_i 个值为 ii 的元素。

对于每个 k=0,1,…,2m−1k=0,1,\ldots,2^m-1,求有多少种方法从 SS 中选择元素,使得所选元素的异或和为 kk,且值为 ii 的所选元素数不超过 bib_i。即使值相同,原集合中的不同元素也可以分别选择。空集的异或和为 00。

每个答案均对 998244353998244353 取模。

输入格式

第一行一个整数 mm。第二行 2m2^m 个整数,第 i+1i+1 个数是 aia_i。第三行 2m2^m 个整数,第 i+1i+1 个数是 bib_i。

输出格式

一行 2m2^m 个整数,第 i+1i+1 个数是 k=ik=i 时的答案。

样例

2
1 2 0 2
1 1 0 2
4 8 8 4

数据范围

1≤m≤201\le m\le20,0≤bi≤ai≤1050\le b_i\le a_i\le10^5。

测试点 特殊限制
1–2 m≤10m\le10,ai≤103a_i\le10^3
3–4 m≤10m\le10
5–7 ai≤103a_i\le10^3
8–10 无

原 PDF 题面