标签：10 frac 起床 SA 数据结构 莫队 mod

AT_joisc2014_c 歴史の研究

该起床了。

该起床了。

该起床了。

该起床了。

该起床了。

本题删除会改变最大值，十分麻烦，所以使用回滚莫队即可。

该起床了。

该起床了。

该起床了。

该起床了。

该起床了。

P3245 [HNOI2016]大数

考虑如何提取区间 \([l,r]\) 组成的数。

设 \(SA_i\) 表示 \(S[i,n]\) 组成的数值，则 \([l,r]\) 组成的数为 \(SU_{l,r}=\frac{SA_l-SA_{r+1}}{10^{n-r}}\) 且统计 \(SU_{l,r}\mod P=0\)。

当 \(10^{n-r}\mod P!=0\) 时:

\[10^{n-r}*\frac{SA_l-SA_{r+1}}{10^{n-r}}\mod P=10^{n-r}*0 \]

\[(SA_l-SA_{r+1})\mod P=0 \]

\[SA_l\mod P=SA_{r+1}\mod P \]

维护 \(SA_i\mod P\) 莫队求区间有多少个相同即可。

当 \(10^{n-r}\mod P==0\) 时，\(P\in\{2,5\}\)。运用 \(2,5\) 倍数特征即可。

标签：10,frac,起床,SA,数据结构,莫队,mod
From： https://www.cnblogs.com/lizhous/p/17416742.html