快速讨伐 ( 一道DP与组合数学的思维好题 )

传送门

前置小技巧 (线性求阶乘的逆元)

根据逆元的定义 : \(a*x \equiv 1 (mod p)\)
所以相当于 $ x== $ \(1\over a\) (在膜意义下)
那么 \(1\over !(n+1)\) 也就相当于 !(n+1) 的逆元，
所以 !n 的逆元就可以看做 \(1\over !n\) 也就是\(1\over !(n+1)\)$ *(n+1)$

题解

显然不管什么情况操作次数一定是固定的，为 \(2*n+\) \(\sum_{i=1}^n\) \(a_i\) 。
我们先不考虑角色等级的情况，即默认初始等级为 n （即已经操作了n次，且全部用来提升人物等级）
那么对于第i次提升装备等级就可以多打败 Ai 个的敌人，
也就是在剩余的操作中，可以任选 Ai 个位置来进行此操作
则会有 \(\binom{ \sum_{k=i}^n a_i +n-i}{a_i}\)

快速讨伐

原文：https://www.cnblogs.com/yzhx/p/11530278.html