题意理解

我们有一个 $n \times m \times k$ 的三维网格，初始时每个格子有 $1$ 个细菌。每天：

• 每个细菌分裂为 $6$ 个新细菌，分别向上下左右前后 $6$ 个方向移动
• 如果移动目标超出边界，该细菌死亡
• 原细菌死亡

求 $d$ 天后在位置 $(a,b,c)$ 的细菌数量，对 $998244353$ 取模。

核心思路

关键观察 1：维度独立性

由于细菌在每个维度上的移动是独立的，我们可以将三维问题分解为三个一维问题：

设 $f_d(x)$ 表示在一维长度为 $n$ 的线上，初始位置 $x_0$ 经过 $d$ 天到达位置 $x$ 的路径数（考虑边界死亡）。

那么三维的答案就是：

$$\text{ans} = f_d^{(x)}(a) \times f_d^{(y)}(b) \times f_d^{(z)}(c) $$

其中 $f_d^{(x)}, f_d^{(y)}, f_d^{(z)}$ 分别对应三个维度。

关键观察 2：一维情况的生成函数

对于一维情况，设 $F_d(x)$ 是第 $d$ 天的生成函数：

初始：$F_0(x) = x^{x_0}$

递推：$F_{d+1}(x) = (x + x^{-1}) \cdot F_d(x)$，但要考虑边界：

实际上，考虑边界后，递推关系为：

$$f_{d+1}(i) = f_d(i-1) + f_d(i+1) \quad \text{对于 } 2 \leq i \leq n-1 $$$$f_{d+1}(1) = f_d(2)$$ $$f_{d+1}(n) = f_d(n-1)$$

关键观察 3：矩阵快速幂解法

一维情况可以写成矩阵形式：

设向量 $\mathbf{v}_d = [f_d(1), f_d(2), \dots, f_d(n)]^T$

则 $\mathbf{v}_{d+1} = M \cdot \mathbf{v}_d$，其中 $M$ 是三对角矩阵：

$$M = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 1 & 0 & 1 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ 0 & 0 & 0 & \cdots & 0 \end{bmatrix} $$

那么 $\mathbf{v}_d = M^d \cdot \mathbf{v}_0$

关键观察 4：特征分解与生成函数

矩阵 $M$ 可以进行特征分解，其特征值为：

$$\lambda_j = 2\cos\left(\frac{\pi j}{n+1}\right), \quad j=1,2,\dots,n $$

对应的特征向量为：

$$u_j(i) = \sqrt{\frac{2}{n+1}} \sin\left(\frac{\pi ij}{n+1}\right) $$

因此：

$$f_d(x) = \sum_{j=1}^n \left[2\cos\left(\frac{\pi j}{n+1}\right)\right]^d \cdot \frac{2}{n+1} \sin\left(\frac{\pi x_0 j}{n+1}\right) \sin\left(\frac{\pi x j}{n+1}\right) $$

关键观察 5：三维组合

最终答案为三个维度的乘积：

$$\text{ans} = \sum_{i=1}^n \sum_{j=1}^m \sum_{l=1}^k \left[2\cos\frac{\pi i}{n+1}\right]^d \left[2\cos\frac{\pi j}{m+1}\right]^d \left[2\cos\frac{\pi l}{k+1}\right]^d \cdot C(i,j,l) $$

其中 $C(i,j,l)$ 包含所有的正弦项系数。

算法优化

优化 1：预处理余弦幂

由于 $d$ 很大，需要快速计算 $\cos^d\theta$。可以使用快速幂，但更高效的是预处理所有需要的余弦值的幂。

优化 2：对称性利用

利用三角函数的对称性减少计算量：

$$\cos\left(\frac{\pi j}{n+1}\right) = \cos\left(\frac{\pi (n+1-j)}{n+1}\right) $$

优化 3：一维特殊情况

当 $m=k=1$ 时（子任务3），问题退化为真正的一维情况，可以直接使用特征分解公式。

优化 4：NTT/FFT 加速

对于三维求和，如果直接计算是 $O(nmk)$ 不可接受。但注意到这个求和具有卷积形式，可以使用多维FFT或NTT加速到 $O(N\log N)$，其中 $N = \max(n,m,k)$。

复杂度分析

直接计算：$O(nmk)$，不可接受（最大 $1.7\times 10^{15}$）

特征分解：$O(n+m+k)$ 预处理，$O(1)$ 查询每个位置

FFT加速：$O(N\log N)$，其中 $N = \max(n,m,k)$

实现细节

模运算处理

• 模数 $998244353$ 是NTT友好质数
• 需要预处理阶乘和逆元
• 注意三角函数的模运算处理

边界情况

• 当 $n,m,k$ 很小时直接DP
• 当 $d=0$ 时直接返回初始值
• 处理边界反射的正确性

总结

本题的核心在于：

1. 问题分解：将三维问题分解为三个独立的一维问题
2. 生成函数：利用特征分解求得一维情况的解析解
3. 算法优化：使用FFT/NTT加速三维卷积计算
4. 数学技巧：特征值分解、三角函数性质、模运算处理

这是一个典型的生成函数 + 特征值分解 + FFT优化的组合数学问题，考察选手将物理过程转化为数学模型并设计高效算法的能力。