AdditionalFile5576.zip

#5576. 「RMI 2025」King of rats

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "kor.h"。

题目描述

题目译自 Romanian Master of Informatics 2025 Day2 T2 「King of rats」

在与鼠群进行了一场压倒性的战斗之后，阿米西亚和雨果不得不逃离维克多·德·阿尔勒伯爵的军队。士兵们驻扎在一条狭窄的道路上，这条路可以表示为一个尺寸为 $2 \cdot n$ 的矩阵。此外，我们知道这条路上总共有 $k$ 名士兵。

阿米西亚和雨果将一种配置的危险度定义为其中士兵群体的数量。更形式化地说，如果我们考虑一个 $2 \times n$ 的二进制矩阵，其中有士兵的位置为 $1$。如果两个单元格的值都为 $1$ 且它们共享一条边，我们就说这两个单元格是连通的。注意这种关系是传递的，也就是说如果单元格 $a$ 和 $b$ 连通，且单元格 $b$ 和 $c$ 连通，那么 $a$ 和 $c$ 也被认为是连通的。一个连通分量是指值为 $1$ 的连通单元格构成的极大子集。危险度就是该矩阵中连通分量的数量。

你的任务是帮助这两位主角求出考虑所有可能配置时的危险度的期望值。每种配置被认为是等概率的。在这种情况下，期望值可以定义为所有可能配置中连通分量数量的平均值。

实现细节

你必须实现以下函数：

void prec(int subtask_id);
int solve(int n, int k);

第一个函数将在评测程序开始时被调用一次。你可以用它进行预处理。

第二个函数应返回给定参数 $n$ 和 $k$ 下的危险度期望值，结果对 $998244353$ 取模。形式化地，设 $M=998244353$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not \equiv 0\pmod M$。返回等于 $p \cdot q^{-1}\pmod M$ 的整数。换句话说，返回一个整数 $x$，使得 $0 \leq x < M$ 且 $x \cdot q \equiv p \pmod M$。

第二个函数将被调用 $t$ 次。这意味着输入中有多个测试用例！

注意： 不要忘记包含头文件 kor.h，否则你会得到编译错误！

样例 1

输入

2 
6 
2 2
5 10 
2000 3 
2000 5 
100 32
150 278

输出

332748119
1
518205646
742082393
368118258
937239298

对于第一个样例的第一个测试用例，可能的配置如下所示：

总共有 $6$ 种配置，其中 $4$ 种只有一个连通分量（注：对角线相邻不算连通，所以另外 $2$ 种配置有 $2$ 个连通分量）。 因此答案是 $\frac{4 \cdot 1+2 \cdot 2}{6}=\frac{8}{6}=\frac{4}{3}$。

样例 2

输入

7 
8 
100000000 0 
100000000 1 
100000000 2 
100000000 3 
5219873 192 
853875838 238 
43782384 1500
58123292 180000

输出

0
1
268791198
806373591
782159797
435727907
712321002
257644694

数据范围与提示

对于所有输入数据，满足：

• $1 \leq t \leq 10$
• $1 \leq n \leq 10^{9}$
• $0 \leq k \leq 10^{6}$
• $k \leq 2 \cdot n$

详细子任务附加限制及分值如下表所示。