首先把这个神秘模型时间倒流一下，问题变成从 \((a,b,c)\) 出发，在这个空间里走 \(d\) 步的方案数。
三维显然是独立的，接下来只考虑 \(d,n,a\) 构成的一维情况。
那么我们其实是对于每个 \(0 \le k \le d\) 都要算出：从 \((0,a)\) 出发，可以走 \((1,1)\) 或 \((1,-1)\)，达到 \(x=k\) 上的方案数；同时不能碰到 \(y=0\) 和 \(y=n+1\)。
我们先考虑钦定走到 \((k,b)\)，那么如果没有这两条直线的 bound，方案数自然是 \([x^{a-b}](x+x^{-1})^k = \binom{k}{(k+a-b)/2}\)。
接下来是经典的反射容斥：用走到 \((k,b)\) 的方案数，减去走到 \((k,-b),(k,2(n+1)-b)\) 的方案数，加上走到 \((k,b-2(n+1)),(k,2(n+1)+b)\) 的方案数……
考虑对于每个终点算贡献，那么显然其不能是 \(n+1\) 的倍数，且容斥系数是 \(-1\) 的，其与 \(a\) 之间所隔的 \(y=j(n+1)\) \((j \in \mathbb Z)\) 的条数，次方。
算法 1
对于 \(n \le \sqrt d\)，我们直接 DP 即可 \(\Theta(nd)\)。
对于 \(n > \sqrt d\)，我们对于所有 \(y=j(n+1)\) 和 \(y=(j+1)(n+1)\) 之间的终点一并维护，则这部分是上指标为 \(k\)，下指标是一段区间的组合数的和。拆成前缀和，利用帕斯卡恒等式即可 \(\Theta(1)\) 维护。共 \(\Theta(\frac{d^2}n)\)。
则时间复杂度为 \(\Theta(d\sqrt d)\)。
算法 2
我们对于终点 \(i\)，记其容斥系数为 \(c_{a-i}\)，则欲求数列 \[ f_k = \sum_{|a-i|\le k} c_i [x^i] (x+x^{-1})^k \]
经过一些处理后，其转置问题是 \[ \sum_{i\ge 0} c_i (x+x^{-1})^i \]
可以 \(\Theta(d \log^2 d)\)。从而原问题也可以 \(\Theta(d \log^2 d)\)。
算法 3
考虑矩阵 \[ \mathbf M_n = \{[|i-j|=1]\}_{i,j=1}^n = \begin{bmatrix} & 1 \\ 1 & & 1 \\ & 1 & & \ddots \\ & & \ddots \end{bmatrix} \]
那么我们欲求 \[ f_k = \sum_{i=1}^n (\mathbf M_n^k)_{a,i} \]
考虑其特征多项式 \[ p_n(\lambda) = \left|\begin{matrix} \lambda & -1 \\ -1 & \lambda & -1 \\ & -1 & \ddots & \ddots \\ & & \ddots \end{matrix}\right| \]
满足一个递推式 \[ p_n = \lambda p_{n-1}-p_{n-2} \]
则可以用 \(\Theta(n \log n)\) 甚至 \(\Theta(n)\) 求出 \(p_n(\lambda)\)，从而可以得到 \(f_k\) 的递推式。
因此关键在于求出 \(f_{0,1,\dots,n-1}\)。注意到此时最多需要反射一次，可以 \(\Theta(n)\) 计算。
不幸的是，最后还有一步 \(\Theta(n\log n)\) 的卷积。
总复杂度 \(\Theta(n\log n)\)。
因为（除了板子以外）算法 2 最好写所以（被拿集训队胡策当）模拟赛的时候写了算法 2。