题目描述
给定一个多重集合 S。对于每个整数 i(0≤i<2m),集合中有 ai 个值为 i 的元素。
对于每个 k=0,1,…,2m−1,求有多少种方法从 S 中选择元素,使得所选元素的异或和为 k,且值为 i 的所选元素数不超过 bi。即使值相同,原集合中的不同元素也可以分别选择。空集的异或和为 0。
每个答案均对 998244353 取模。
输入格式
第一行一个整数 m。第二行 2m 个整数,第 i+1 个数是 ai。第三行 2m 个整数,第 i+1 个数是 bi。
输出格式
一行 2m 个整数,第 i+1 个数是 k=i 时的答案。
样例
2
1 2 0 2
1 1 0 2
4 8 8 4
数据范围
1≤m≤20,0≤bi≤ai≤105。
| 测试点 |
特殊限制 |
| 1–2 |
m≤10,ai≤103 |
| 3–4 |
m≤10 |
| 5–7 |
ai≤103 |
| 8–10 |
无 |
原 PDF 题面