QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#4903. 细菌

Statistics

科学家们搭建了一个巨大的细菌培养箱。这个培养箱是一个巨大的长方体,其长、宽、高分别为 $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\leq d,n,m,k \leq 1.2 \times 10^5,1 \leq a \leq n,1 \leq b \leq m,1 \leq c \leq k$。

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

  • 子任务 1($5$ 分):$d,n,m,k \leq 50$。
  • 子任务 2($10$ 分):$d,n,m,k \leq 5×10^3$。依赖子任务 1。
  • 子任务 3($15$ 分):$m=k=1$。
  • 子任务 4($10$ 分):$k=1$,$n,m \geq d$。
  • 子任务 5($15$ 分):$k=1$,$n,m \geq \frac{d}{10}$。依赖子任务 4。
  • 子任务 6($35$ 分):$k=1$。依赖子任务 3、4、5。
  • 子任务 7($10$ 分):无特殊限制。依赖子任务 1、2、3、4、5、6。

时空限制

时间限制:$\texttt{2s}$。

空间限制:$\texttt{512MB}$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.