2020.10.17 T2 fight

发表于 更新于 分类于

题目

小七擅长泰拳，某天他打算与小枣切磋拳技，一共需要进行 \(n\) 次比赛。

由于双方拳技难分上下，每场比赛小七获胜或落败的概率都是 \(\dfrac{1}{p+2}\) ，平局 的概率是 \(\dfrac{p}{p+2}\) 。 若最后小七获胜场数大于落败场次，且平局次数为$ k$ ，则能获得 \(k + 1\) 奖励分。

小七想知道，他能获得的奖励分的期望是多少呢？为了避免精度误差，你需 要输出答案在模 \(998244353\) 意义下的结果。

分析

为了方便，可以假定胜，负各有 \(1\) 种方案，平局有 \(p\) 种方案，最后将答案乘上$(p + 2)^{-n} $即可。

枚举有 \(i\) 次胜或负，有 \(n-i\) 场平局，此时胜场大于负场的方案数是 \((x + x^{-1})^i\)展开后次数 \(> 0\) 的项系数之和，即 \((x^2 + 1)^i\) 展开后次数$ > i$ 的项系数之和。

将 \((x^2 + 1)^i\) 用二项式定理直接展开并计算答案，时间复杂度 \(O(n^2)\) ，期望得分\(40\) 分。

考虑优化计算 \((x^2 + 1)^i\) 展开后次数 \(> i\) 的项系数之和，记其为 \(t(i)\)。

用二项式定理可以得到 $t(i) = ∑^{i}_{j=0}[2j > i] x^{2j} $。当 \(i\) 为奇数时，每个 $2j > i $的一定对应了一个 $2(i-j) < i $，

所以 \(t(i)\) 一定是所有系数之和的一半，即 \(t(i) = 2^{i-1}\) 。当 \(i\) 为偶数时，只需要减掉 $j = \(这一项系数，剩下的同样一一对 应，\)t(i) = $。

时间复杂度 \(O(n)\) ，期望得分 \(100\) 分。