自动搬运

查看原文

来自洛谷，原作者为

	RyanLi 跟着光，靠近光，成为光，散发光。

搬运于2025-08-24 21:16:05，当前版本为作者最后更新于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;
}

视频讲解

完整代码见视频题解