题解：P10893 城市化发展委员会

Walter_Fang · 2024-08-22 23:01:20 · 题解

笑点解析：昨天写完没点申请题解，今天题解申请通道关了。

看到很多大佬写了 STL 和单调数据结构做法，这里给个思维含量颇高的数学做法。

题目描述

规定一个序列为“安全的”当且仅当这个序列的所有前缀和为正数。

给定一个长度为 n 的序列 A_i，执行 n 次以下操作得出新的数列 A_{i+1}：

• 若 A_i 是安全的，将其接到 A_{i+1} 末尾。
• 将 A_i 循环左移 1 位。

求 \dfrac{|A_{k+1}|}{|A_k|}，答案对 998244353 取模。

思路解析

设所求答案 f(i)=\dfrac{|A_{i+1}|}{|A_i|}，g(i)=\sum^i_{j=1}A_{ij}，易证 f(i)=g(i)。 于是 f(i+1)=g(i+1)=f(i)g(i)=f(i)^2。所以 f(k)=g(0)^{2^k}。写个快速幂就行了，理论上可以用费马小定理再优化一下，没试。

不放代码。