CF2172D Divisor Card Game

在台湾，许多数学教师设计了棋盘与卡牌类游戏，帮助学生理解复杂的数学概念。近日，一款特别的卡牌游戏在小学和中学教师之间广受欢迎，因为它不仅能有效帮助学生掌握约数和倍数的概念，同时对于师生都极具趣味性。 游戏的规则如下：教师准备 $n$ 张不同的卡牌，编号为 $1$ 到 $n$。第 $i$ 张卡牌上写有整数 $a_i$，并且整数 $a_1, a_2, \dots, a_n$ 严格递增。 有 $m$ 位学生，编号为 $1$ 到 $m$，参与游戏。游戏开始前，每位学生分到一组非空的不相交卡牌子集。任意两名学生分到的卡牌没有重合，且至少有一张卡牌未被分配。 记初始时未被分配的卡牌数量为 $k$。游戏共进行 $k$ 轮。每轮依次进行以下步骤： 1. 教师从剩余未分配的卡牌中均匀随机选出一张，公开该卡牌。记这张卡牌上写的整数为 $c$。 2. 每位学生同时从自己手中选择恰好一张卡牌。 3. 该牌的归属规则如下： - 对所有学生选出的卡牌，找出卡牌值可以被 $c$ 整除的那些。 - 若存在至少一张满足条件的卡牌，则选出其中值最小的那一张，对应的学生获得本轮公开的卡牌，并将其加入自己的集合。 - 若没有任何选出的卡牌满足能被 $c$ 整除，则该卡牌弃置（无人获得）。弃置的卡牌不会再出现在后续轮次。 每位学生在整个游戏过程中均采用相同的策略： - 如果学生手中至少有一张卡牌值能够被 $c$ 整除，则选择其中值最小的那张； - 否则，选择手中值最小的卡牌。 假设所有学生始终按照上述策略出牌，求游戏结束后每位学生期望拥有的卡牌数量。

第一行包含两个整数 $n$ 和 $m$，分别表示卡牌总数和学生人数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 为第 $i$ 张卡牌上的整数。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，其中 $b_i$ 表示第 $i$ 张卡牌开始时的归属关系：若 $b_i \ne 0$，则归属于第 $b_i$ 位学生，若 $b_i = 0$，则为未分配。 - $1 \leq m < n \leq 600$ - $1 \le a_i \le 10^{18}$ - $0 \leq b_i \leq m$ - 对于所有 $1 \le i < n$，有 $a_i < a_{i + 1}$ - 对 $j=0,1,\ldots,m$，至少存在一个 $i$ 使得 $b_i=j$

输出 $m$ 个数，第 $i$ 个数表示第 $i$ 位学生在游戏结束时期望拥有的卡牌数。 可以证明，答案可表示为一个分数 $\frac{p}{q}$，其中 $q$ 不是 $998244353$ 的倍数。你需要输出 $p\times q^{-1} \bmod 998244353$，其中 $q^{-1}$ 表示 $q$ 在 $998244353$ 下的乘法逆元。

由 ChatGPT 5 翻译