菜练菜练。

时间线

• 19:10-19:14 写 T1
• 19:14-19:21 写 T2
• 19:21-19:26 写 T3
• 19:26-19:35 写 T4
• 19:35-19:55 写 T5
• 19:55-21:00 写 T6

得分

错因分析

C 绿

知识点：快速幂，数学
错因：没有注意到 很大，直接与 相乘做快速幂的指数很可能会 爆 long long。
检查时一定要注意数据范围，太大了一定要多取模，或者转化为两次快速幂。

D 青

知识点：二分
错因：没有特判掉 或 的情况。
注意特殊情况，有可能不满足限制。

E 蓝

知识点：dp，数学
错因：想了一个错误的贪心，没有证明或举反例。
贪心一定要考虑证明或举反例，不能按照感觉瞎猜。

首先，每执行一次操作，数字至少乘以 2，所以做的操作次数是 级别的。定义 表示经过 次操作得到 的最小花费，转移时枚举 的倍数即可。状态数是 级别的，枚举倍数是 级别的，所以预处理的时间复杂度是 。对于每个询问，如果 超过了 最多分解的质因数个数 ，则 。输出 即可。

F_紫

知识点：数学，计数
错因：想太久了，取模不够多，赛时时间不够，没调出来。
菜练菜练。

法一：矩乘快速幂加速线性递推

令 表示到当前位置为止，全 0 的方案数， 表示以 1 结尾的方案数。

• 时，；
• 时，。

出现了线性递推关系，我们可以用矩阵维护。先求出整个字符串的转移矩阵，再做快速幂，乘上初始的矩阵 即可。

法二：数学

枚举每一个 1 作为第一个 1 的情况，假设前面有 个 0，后面有 个 1，则单个 字符串内的贡献是 ，累加。考虑多出的 个 怎么处理。设 中有 个 0， 个 1，枚举前面有多少个 ，累加后得到 ，令 ，转化为等比数列求值，注意特判 的情况。记得加上全是 0 的方案数。，所以要用费马小定理来降低次数。