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

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

看到很多大佬写了 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}$。写个快速幂就行了，理论上可以用费马小定理再优化一下，没试。

不放代码。