---

题目大意

我们有两种奥术宝石：

• 2型：$k$ 个核心，每个核心是 $2 \times n$ 网格，用 $1 \times 2$ 骨牌铺满
• 3型：$k$ 个核心，每个核心是 $3 \times n$ 网格，用 $1 \times 2$ 骨牌铺满

定义：

• $F(n,k)$：2型宝石，宽度 $n$，$k$ 个核心的不同咒术数
• $G(n,k)$：3型宝石，宽度 $n$，$k$ 个核心的不同咒术数

咒术：$k$ 个核心的填充方案互不相同的有序组合。

问题：给定 $l, r, k$，求

$$\mathrm{ans} = \frac{1}{r-l+1} \sum_{n=l}^r F(n,k) \quad (\text{或 } G(n,k)) $$

结果对 $998244353$ 取模。

---

第一步：理解 $F(n,k)$ 和 $G(n,k)$ 的组合意义

设 $a_n$ 表示 $2 \times n$ 网格的骨牌铺满方案数（2型），$b_n$ 表示 $3 \times n$ 网格的骨牌铺满方案数（3型）。

那么：

• 从 $a_n$ 种方案中选出 $k$ 个互不相同的方案，有序排列，就是 $F(n,k)$
• 同理 $G(n,k)$ 是从 $b_n$ 种方案中选 $k$ 个互不相同的方案有序排列

因此：

$$F(n,k) = a_n \cdot (a_n - 1) \cdots (a_n - k + 1) = \frac{a_n!}{(a_n - k)!} $$$$G(n,k) = b_n \cdot (b_n - 1) \cdots (b_n - k + 1) = \frac{b_n!}{(b_n - k)!} $$

（当 $k > a_n$ 时 $F(n,k) = 0$，同理 $G(n,k)$）

---

第二步：求 $a_n$ 和 $b_n$ 的递推式

2型宝石 $2 \times n$ 网格铺骨牌

经典问题，递推关系：

$$a_0 = 1,\ a_1 = 1,\ a_n = a_{n-1} + a_{n-2}$$

即 $a_n$ 是斐波那契数列：

$$a_n = \text{Fib}_{n+1}$$

具体：

• $a_0=1, a_1=1, a_2=2, a_3=3, a_4=5, a_5=8, \dots$

3型宝石 $3 \times n$ 网格铺骨牌

经典递推：

$$b_0 = 1,\ b_1 = 0,\ b_2 = 3$$ $$b_n = 4b_{n-2} - b_{n-4} \quad (n \ge 4)$$

或者另一种形式：

$$b_n = 4b_{n-2} - b_{n-4}$$

其中 $b_3=0, b_4=11, b_5=0, b_6=41, \dots$（$n$ 为奇数时 $b_n=0$）

但题目中 $n$ 应该是任意正整数，这里可能 $3 \times n$ 在 $n$ 为奇数时无法铺满？样例中 $G(2,2)=3$ 对应 $b_2=3$ 正确。

实际上标准递推是：

$$b_0=1, b_2=3, b_4=11, b_6=41,\dots$$ $$b_n = 4b_{n-2} - b_{n-4}$$

对于奇数 $n$，$b_n=0$。

---

第三步：将 $F(n,k)$ 和 $G(n,k)$ 写成多项式形式

定义下降阶乘幂：

$$x^{\underline{k}} = x(x-1)\cdots(x-k+1)$$

则：

$$F(n,k) = a_n^{\underline{k}}, \quad G(n,k) = b_n^{\underline{k}} $$

我们可以将 $x^{\underline{k}}$ 展开为普通多项式：

$$x^{\underline{k}} = \sum_{j=0}^k s(k,j) x^j$$

其中 $s(k,j)$ 是第一类斯特林数（带符号）。

因此：

$$F(n,k) = \sum_{j=0}^k s(k,j) a_n^j$$ $$G(n,k) = \sum_{j=0}^k s(k,j) b_n^j$$

---

第四步：求和转化为线性递推数列求和

我们需要计算：

$$S = \sum_{n=l}^r F(n,k) = \sum_{j=0}^k s(k,j) \sum_{n=l}^r a_n^j $$

（对 $G$ 同理）

问题转化为：对每个 $j$，计算 $\sum_{n=l}^r a_n^j$。

---

第五步：利用线性递推数列的性质

对 $a_n$（斐波那契数列）

$a_n$ 满足线性递推：

$$a_n = a_{n-1} + a_{n-2}$$

特征方程：$x^2 - x - 1 = 0$

对于线性递推数列，$a_n^j$ 也满足某个线性递推（根据 Cayley–Hamilton 定理），递推阶数至多 $(j+1)$。

因此我们可以：

1. 找到 $a_n^j$ 的线性递推关系
2. 用矩阵快速幂求前 $n$ 项和

对 $b_n$（$3 \times n$ 铺砖数列）

$b_n$ 满足：

$$b_n = 4b_{n-2} - b_{n-4}$$

特征方程：$x^4 - 4x^2 + 1 = 0$

同样，$b_n^j$ 也满足线性递推。

---

第六步：具体算法步骤

预处理：

1. 计算斯特林数 $s(k,j)$ 对 $998244353$ 取模，$k \le 501$
2. 对每个 $j=0..k$，找到 $a_n^j$ 和 $b_n^j$ 的线性递推关系

对每个询问 $(l,r,k)$：

1. 对 $j=0..k$：
   • 计算 $A_j = \sum_{n=l}^r a_n^j$（用矩阵快速幂求线性递推数列区间和）
2. $ans = \frac{1}{r-l+1} \sum_{j=0}^k s(k,j) A_j \bmod 998244353$

---

第七步：处理大范围 $l,r \le 10^{18}$

由于 $l,r$ 巨大，我们必须用矩阵快速幂来计算线性递推的区间和。

对于线性递推：

$$u_n = c_1 u_{n-1} + c_2 u_{n-2} + \dots + c_m u_{n-m} $$

我们可以构造转移矩阵 $M$，使得：

$$\begin{bmatrix} u_n \\ u_{n-1} \\ \vdots \\ u_{n-m+1} \end{bmatrix} = M \cdot \begin{bmatrix} u_{n-1} \\ u_{n-2} \\ \vdots \\ u_{n-m} \end{bmatrix} $$

并且前缀和 $S_n = \sum_{i=1}^n u_i$ 也可以通过扩展矩阵来递推。

---

第八步：实现细节

对 $a_n^j$（斐波那契的幂）：

斐波那契数列的 $j$ 次幂的线性递推阶数 = $j+1$（实际上更小，但上界是 $j+1$）

我们可以用矩阵：

$$\begin{bmatrix} a_n^j & a_{n-1}^j & \dots & a_{n-j}^j \end{bmatrix} $$

但更简单的方法：直接对向量 $(a_n, a_{n-1})$ 做矩阵快速幂得到 $a_n$，然后快速幂求 $a_n^j$？不行，$n$ 太大。

正确方法：利用 $a_n$ 的线性递推性质，$a_n^j$ 也线性递推，用 Berlekamp–Massey 算法找到递推式，然后矩阵快速幂求和。

对 $b_n^j$（3型铺砖的幂）：

$b_n$ 本身递推阶数=4，$b_n^j$ 的递推阶数 $\le 4j$。

---

第九步：复杂度分析

• 斯特林数预处理：$O(k^2)$
• 对每个 $j$，矩阵大小 $O(j)$，矩阵快速幂 $O(j^3 \log r)$
• 总复杂度：$O(k \cdot k^3 \log r) = O(k^4 \log r)$

$k \le 501$，$k^4 \approx 6\times 10^{10}$ 太大，需要优化。

实际上 $a_n^j$ 的递推阶数 $\le j+1$，但 $j \le 501$，矩阵大小 $\le 502$，$502^3 \approx 1.3\times 10^8$，再乘 $\log r \approx 60$，约 $8\times 10^9$，仍很大。

需要进一步优化：

• 利用斐波那契的闭形式（通项公式）$a_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$，其中 $\phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2}$
• 那么 $a_n^j = 5^{-j/2} (\phi^n - \psi^n)^j$
• 二项展开：$a_n^j = 5^{-j/2} \sum_{t=0}^j \binom{j}{t} (-1)^t \phi^{n(j-t)} \psi^{nt}$
• 于是 $\sum_{n=l}^r a_n^j = 5^{-j/2} \sum_{t=0}^j \binom{j}{t} (-1)^t \sum_{n=l}^r (\phi^{j-t} \psi^t)^n$

这是一个等比数列求和，可以直接公式计算。

---

第十步：最终算法（对2型宝石）

1. 预处理组合数和斯特林数
2. 计算 $\phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2}$ 在模 $998244353$ 下的值（可能需要扩域）
3. 对每个 $j=0..k$：

$$ A_j = \sum_{n=l}^r a_n^j = 5^{-j/2} \sum_{t=0}^j \binom{j}{t} (-1)^t \frac{(\phi^{j-t}\psi^t)^l - (\phi^{j-t}\psi^t)^{r+1}}{1 - \phi^{j-t}\psi^t} $$

（注意处理公比为1的情况） 4. $ans = \frac{1}{r-l+1} \sum_{j=0}^k s(k,j) A_j$

对3型宝石，$b_n$ 也有闭形式（涉及 $\sqrt{3}$），类似处理。

---

总结

本题的关键步骤：

1. 将咒术数转化为下降阶乘幂
2. 利用斯特林数展开为普通幂次和
3. 利用线性递推数列的闭形式，将区间和转化为等比数列求和
4. 模意义下处理无理数（扩域或找模平方根）

这样可以在 $O(k^2 \log r)$ 时间内处理每个询问，满足大数据要求。