#P6692. [2019山东省队集训第一轮]梦批幼

    ID: 6542 传统题 1500ms 512MiB 尝试: 4 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-概率与期望指示变量期望线性性组合数学补集计数容斥原理排序与序列处理多维前缀和单调栈数论快速幂模逆元CF2700

[2019山东省队集训第一轮]梦批幼

[2019山东省队集训第一轮]梦批幼

题目背景

神树大人与神 J:另一个夏天发生的故事。

神树大人和神 J(Joker)热衷于创造各种各样的宇宙。神树大人负责编写底层框架;神 J 创造了可以用极高抽象程度描述世界的语言 Jode。他们生活在所有宇宙之外的地方,那里的一切也由他们创造。

一天,神 J 走出神树旁边的小屋,发现神树大人掉了许多树叶,手里还拿着《哈利波特与阿兹卡班的囚徒》。神树大人苦恼于他们创造的宇宙都可以由神 J 机模拟,而“时间转换器”似乎需要用未来的信息计算过去。神 J 张了张嘴,又闭上了。一人一树坐在一起,久久没有答案。

题目描述

有一个大小为 n×m×kn\times m\times k 的整点网格,点的坐标满足 1≤x≤n1\le x\le n、1≤y≤m1\le y\le m、1≤z≤k1\le z\le k。

一个子长方体由三个非空连续整数区间的笛卡尔积组成,包含边界上的所有整点;每个维度都可以只包含一个坐标。因此子长方体总数为

C=n(n+1)m(m+1)k(k+1)8.C=\frac{n(n+1)m(m+1)k(k+1)}8.

每个点有权值 valx,y,zval_{x,y,z},其中一些点是障碍。

神树大人独立进行 ww 次选择,每次从全部 CC 个子长方体中等概率选择一个,选中其中的所有点。同一个子长方体和同一个点都可以被重复选中。

这 ww 次选择的收益规定如下:

  • 如果有任何障碍被选中,收益为 00;
  • 否则,收益为至少被选中过一次的点的权值之和,每个点只计算一次。

求收益的期望,对 998244353998244353 取模。将有理数表示为分子、分母后,用分母的模逆元计算。

输入格式

第一行四个整数 n,m,k,wn,m,k,w。

接下来 nmnm 行,每行 kk 个 0/10/1 整数。第 (x−1)m+y(x-1)m+y 行的第 zz 个数描述点 (x,y,z)(x,y,z):00 表示障碍,11 表示非障碍。

再接下来 nmnm 行,每行 kk 个整数。第 (x−1)m+y(x-1)m+y 行的第 zz 个数为 valx,y,zval_{x,y,z}。

输出格式

输出一行一个整数,表示期望对 998244353998244353 取模后的结果。

样例输入 1

1 2 2 1
1 0
0 1
1 19260817
20010910 4

样例输出 1

221832079

样例解释 1

一共有 99 个子长方体。其中只有两个不含障碍,它们分别是权值为 11 和 44 的单点子长方体;其余选择收益均为 00。

因此期望为 5/95/9,其模意义下的值为 221832079221832079。

样例输入 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

数据范围

所有数据满足 n,m,k≤60n,m,k\le60,w≤109w\le10^9,valx,y,z≤109val_{x,y,z}\le10^9。

子任务 分值 n,m,kn,m,k 的上界 ww 的上界
1 10 分 1010 11
2 30 分 2020 10910^9
3 60 分 6060