游戏装备印记期望收益的动态规划解法

1. 题目背景与问题建模

这道题目源自一个Roguelike游戏的装备系统设定。在游戏中，装备通过融合可以继续成长，而融合过程中需要从原有装备中抽取印记。每个印记槽中有无限多个同种印记，我们需要计算在随机抽取k次后的期望收益。

1.1 游戏机制转化为数学模型

将游戏机制转化为数学问题：

• 有n个印记槽，每个槽中的印记价值为a_i
• 机械臂初始位置任意
• 每次抽取后可以停留在原地或向右移动任意格
• 进行k次抽取，总收益为k个印记价值的乘积
• 需要计算所有可能操作序列的收益平均值

1.2 关键问题分析

这个问题本质上是在计算所有可能的k次抽取序列的收益平均值。由于机械臂可以停留在原地或向右移动，这实际上构成了一个"非递减路径"问题，其中每一步的选择会影响后续的可能性。

2. 动态规划解法设计

2.1 状态定义

我们使用两个动态规划数组：

• F[i][j]：表示前i个槽中进行j次操作的总路径数
• G[i][j]：表示前i个槽中进行j次操作的所有路径的收益总和

使用滚动数组技巧优化空间复杂度，因为每次只依赖前一个状态。

2.2 状态转移方程

对于第i个槽：

1. 路径数转移：
   F[i][j] = F[i-1][j] + F[i][j-1]
   这表示可以从前i-1个槽直接转移过来，或者在前i个槽中多操作一次

2. 收益总和转移：
   G[i][j] = G[i-1][j] + G[i][j-1] * a_i
   同样分为两部分：前i-1个槽的收益总和，以及在前i个槽多操作一次带来的收益变化

2.3 初始化条件

F[0][0] = 1（初始状态）
G[0][0] = 1（初始状态）

3. 模运算与逆元处理

3.1 为什么需要模运算

由于结果可能很大且需要输出分数形式，我们使用模19260817运算。但直接除法在模运算中不适用，需要使用模逆元。

3.2 费马小定理的应用

根据费马小定理，在模素数p下，a的逆元是a^(p-2)。因此：
平均值 = G[n][k] / F[n][k] ≡ G[n][k] * F[n][k]^(p-2) mod p

3.3 快速幂实现

代码中实现了快速幂函数pwr()，用于高效计算模逆元：

cpp复制