B3944 题解

RyanLi · 2024-03-10 20:35:43 · 题解

Source & Knowledge

2024 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

新型病毒 91-DIVOC 正在广泛传播。

第一天有 a 个人被感染，在接下来的每天中，每个感染者都会传染给另外的 q 个人。定义传染系数为每天被感染的的人数的乘积，求 k 天内的传染系数对 722733748 取模的结果。

题目分析

根据题意：

• 第一天有 a 个人被感染。
• 在第二天时，这 a 个人中每个人都会传染给另外的 q 个人，因此第二天就有了 a \times q 个人被感染。
• 第三天时，这 a \times q 个人中每个人又会传染给另外的 q 个人，因此第三天就有 a \times q \times q 个人被感染。

以此类推，我们可以发现到第 k 天时，被感染的人数为 a \times \underbrace{q \times \cdots \times q}_{k - 1 \ 个}。

求出了每天被感染的人数，只需要将它们乘起来就可以得到 k 天内的传染系数。由于答案可能很大，因此我们需要边乘边取模。

cin >> k >> a >> q;
for (int i = 1; i <= k; ++i) {
    ans = ans * a % 722733748;
    a = a * q % 722733748;
}

视频讲解

完整代码见视频题解