#P6692. [2019山东省队集训第一轮]梦批幼
[2019山东省队集训第一轮]梦批幼
[2019山东省队集训第一轮]梦批幼
题目背景
神树大人与神 J:另一个夏天发生的故事。
神树大人和神 J(Joker)热衷于创造各种各样的宇宙。神树大人负责编写底层框架;神 J 创造了可以用极高抽象程度描述世界的语言 Jode。他们生活在所有宇宙之外的地方,那里的一切也由他们创造。
一天,神 J 走出神树旁边的小屋,发现神树大人掉了许多树叶,手里还拿着《哈利波特与阿兹卡班的囚徒》。神树大人苦恼于他们创造的宇宙都可以由神 J 机模拟,而“时间转换器”似乎需要用未来的信息计算过去。神 J 张了张嘴,又闭上了。一人一树坐在一起,久久没有答案。
题目描述
有一个大小为 的整点网格,点的坐标满足 、、。
一个子长方体由三个非空连续整数区间的笛卡尔积组成,包含边界上的所有整点;每个维度都可以只包含一个坐标。因此子长方体总数为
每个点有权值 ,其中一些点是障碍。
神树大人独立进行 次选择,每次从全部 个子长方体中等概率选择一个,选中其中的所有点。同一个子长方体和同一个点都可以被重复选中。
这 次选择的收益规定如下:
- 如果有任何障碍被选中,收益为 ;
- 否则,收益为至少被选中过一次的点的权值之和,每个点只计算一次。
求收益的期望,对 取模。将有理数表示为分子、分母后,用分母的模逆元计算。
输入格式
第一行四个整数 。
接下来 行,每行 个 整数。第 行的第 个数描述点 : 表示障碍, 表示非障碍。
再接下来 行,每行 个整数。第 行的第 个数为 。
输出格式
输出一行一个整数,表示期望对 取模后的结果。
样例输入 1
1 2 2 1
1 0
0 1
1 19260817
20010910 4
样例输出 1
221832079
样例解释 1
一共有 个子长方体。其中只有两个不含障碍,它们分别是权值为 和 的单点子长方体;其余选择收益均为 。
因此期望为 ,其模意义下的值为 。
样例输入 2
3 3 3 314517734
1 1 1
1 1 1
1 0 0
1 1 1
0 1 1
1 1 0
1 1 0
1 0 1
1 1 1
817262110 136540228 799866270
723030147 493813645 462933092
410144187 437368402 92260608
417876498 198541430 698346906
7035108 699429927 852478079
284809098 741309134 601136066
351432938 717459664 276984303
835086023 44654510 826918947
269829027 582872667 662317096
样例输出 2
249376928
数据范围
所有数据满足 ,,。
| 子任务 | 分值 | 的上界 | 的上界 |
|---|---|---|---|
| 1 | 10 分 | ||
| 2 | 30 分 | ||
| 3 | 60 分 |