题目描述#

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

给定一个长度为 $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}$。写个快速幂就行了，理论上可以用费马小定理再优化一下，没试。

不放代码。