#2027. 细菌

细菌

细菌

题目描述

标题: 细菌 - Problem - QOJ.ac

#4903. 细菌

Statistics

The problem was used in the following contests:

科学家们搭建了一个巨大的细菌培养箱。这个培养箱是一个巨大的长方体,其长、宽、高分别为 n,m,k,被划分为 n×m×k 个 1×1×1 的小格。我们建立一个三维空间直角坐标系,用 (x,y,z)(1≤x≤n,1≤y≤m,1≤z≤k) 来描述一个小格的位置。

在实验开始的时候,每个小格都恰有 1 个细菌。接下来每天,所有细菌都会分裂。设一个在 (x,y,z) 的细菌发生分裂,它会分裂产生 6 个新细菌,分别前往坐标为 (x+1,y,z),(x−1,y,z),(x,y+1,z),(x,y−1,z),(x,y,z+1),(x,y,z−1) 的小格。原来的细菌则死亡。特别地,如果一个细菌前往的小格并不存在,则该细菌会当场死亡。

实验将进行连续 d 天。在 d 天结束后,科学家们想知道:在坐标为 (a,b,c) 的小格有多少细菌?由于答案可能很大,你只需要输出它对 998244353 取模后的值即可。

输入格式

一行七个正整数 d,n,m,k,a,b,c。

输出格式

一行一个整数表示答案 998244353 取模后的值。

输入输出样例 1

输入

2 2 2 3 1 1 1

输出

10

解释

第一天结束后,可以知道:所有 z=2 的格子都恰有 4 个细菌,其余格子都恰有 3 个细菌。而第二天结束后,格子 (1,1,1) 的细菌数量等于第一天结束时 (1,1,2),(1,2,1),(2,1,1) 的细菌数量总和,即为 10。

输入输出样例 2

输入

2 2 2 3 1 1 2

输出

14

输入输出样例 3

输入

50 49 44 48 49 15 25

输出

544847893

输入输出样例 4

输入

120000 49997 49997 49993 46278 44140 26931

输出

139550295

数据范围与约定

对于全部数据,1≤d,n,m,k≤1.2×105,1≤a≤n,1≤b≤m,1≤c≤k。

本题设有若干个子任务。对于每个子任务,你必须通过其中的全部测试点来获得这个子任务的分数。

  • 子任务 1(5 分):d,n,m,k≤50。
  • 子任务 2(10 分):d,n,m,k≤5×103。依赖子任务 1。
  • 子任务 3(15 分):m=k=1。
  • 子任务 4(10 分):k=1,n,m≥d。
  • 子任务 5(15 分):k=1,n,m≥d10。依赖子任务 4。
  • 子任务 6(35 分):k=1。依赖子任务 3、4、5。
  • 子任务 7(10 分):无特殊限制。依赖子任务 1、2、3、4、5、6。

时空限制

时间限制:2s。

空间限制:512MB。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2 2 3 1 1 1
10

样例 2

2 2 2 3 1 1 2
14