https://atcoder.jp/contests/arc099/tasks/arc099_d?lang=en
对一个极长的数组进性N次操作，操作有四种。
初始指针指向0，所有数组元素都是0.
两种操作左右移动指针。
两种操作加减指针指向的元素。
问有多少子区间的操作，【单独执行】的结果，等于所有操作执行的结果。
因为实际操作的数组长度和n有关，顶多25000。并且数字种类不会很多，可以考虑哈希。
定义 p r e ( i , j ) pre(i,j) pre(i,j)表示第i次操作后，数组前j位的哈希值。（假设数组长度是M）
整个数组在第i次操作后的哈希值可以这样计算： h ( i ) = p r e ( i , M ) = ∑ j = 0 M − 1 A [ i ] [ j ] ∗ ( B a s e ) j h(i) = pre(i, M) = \sum_{j = 0}^{M - 1} A[i][j] * (Base)^j h(i)=pre(i,M)=j=0∑M−1A[i][j]∗(Base)j 实际上我们不需要遍历数组来得到 p r e ( i , M ) pre(i, M) pre(i,M)，写出公式是为了方便下面理解，为方便直接记作 h ( i ) h(i) h(i)
定于 s i g n ( i ) sign(i) sign(i)表示第i次操作的符号： $$
\begin{equation} sign(i)=\left{ \begin{aligned} 0 & , \ S_i \ is \ < or \ > \ 1 & , \ S_i \ is \ + \ -1 & , \ S_i \ is \ - \end{aligned} \right. \end{equation} $$ 定义 p ( i ) p(i) p(i)表示第i次操作以后，当前的下标。
由于每次操作至多使得一个数字+1，并且我们知道每次改变的位置。
根据第一个公式，可以列出 h ( i ) h(i) h(i)的递推式： h ( i ) = h ( i − 1 ) + s i g n ( i ) × ( B a s e ) p ( i ) h ( i ) = h ( 0 ) + ∑ k = 1 i s i g n ( k ) × ( B a s e ) p ( k ) h(i) = h(i - 1) + sign(i) \times (Base)^{p(i)} \\ h(i) = h(0) + \sum_{k = 1}^{i} sign(k) \times (Base)^{p(k)} h(i)=h(i−1)+sign(i)×(Base)p(i)h(i)=h(0)+k=1∑isign(k)×(Base)p(k) 可以发现，每一步操作以后的哈希值，是一种类似前缀和的形式。
那么可以容易联想到整个问题要求统计的条件就是： [ h ( R ) − h ( L − 1 ) = = h ( N ) ] [h(R) - h(L - 1) == h(N)] [h(R)−h(L−1)==h(N)] 但这样是不对的。因为题目还有一个隐含的条件是【单独执行】。
【单独执行】意味着， 你取出来的操作区间，也要从 p ( 0 ) p(0) p(0)开始移动指针。
但显然， h ( R ) − h ( L − 1 ) h(R) - h(L - 1) h(R)−h(L−1)这个区间的操作结果，是从 p ( L − 1 ) p(L - 1) p(L−1)开始的。
那么需要考虑的就是，如何让这个区间所有操作的相对位置，都偏移到和从 p ( 0 ) p(0) p(0)等价。
这就可以借助幂的性质： [ h ( R ) − h ( L − 1 ) ( B a s e ) p ( L − 1 ) − p ( 0 ) = = h ( N ) ] [\frac{h(R) - h(L - 1)}{(Base)^{p(L - 1) - p(0)}} == h(N)] [(Base)p(L−1)−p(0)h(R)−h(L−1)==h(N)] 可以这样理解： h ( i ) h(i) h(i)就是一堆幂的和，指数代表了这些操作的位置，那只要每个幂的指数都减去一个偏移量，就相当于所有操作都偏移过去了。
于是我们可以把问题转化成统计： ∑ ∑ [ h ( R ) = = h ( N ) × ( B a s e ) p ( L − 1 ) − p ( 0 ) + h ( L − 1 ) ] ∑ r = 1 N ∑ l = 0 r − 1 [ h ( r ) = = h ( N ) × ( B a s e ) p ( l ) − p ( 0 ) + h ( l ) ] \sum \sum [h(R) == h(N) \times (Base)^{p(L - 1) - p(0)} + h(L - 1)] \\ \sum_{r = 1}^{N} \sum_{l = 0}^{r - 1} [h(r) == h(N) \times (Base)^{p(l) - p(0)} + h(l)] ∑∑[h(R)==h(N)×(Base)p(L−1)−p(0)+h(L−1)]r=1∑Nl=0∑r−1[h(r)==h(N)×(Base)p(l)−p(0)+h(l)] 这一步可以用map去统计。
p ( i ) p(i) p(i) 很容易变成负的，那么我的处理就是再记一个逆元数组q[i]。
因为就算指数是负数的，也不影响我们最初哈希值的定义（取模意义下）： h ( i ) = p r e ( i , M ) = ∑ j = 0 M − 1 A [ i ] [ j ] ∗ ( B a s e ) j h(i) = pre(i, M) = \sum_{j = 0}^{M - 1} A[i][j] * (Base)^j h(i)=pre(i,M)=j=0∑M−1A[i][j]∗(Base)j 可以看我代码中对这个做了讨论，把对应的逆元取出来即可。
inline ll bpow(int i, int j) { if (i < 0) { return q[-i][j]; } else { return b[i][j]; } }假设数组每个数h[i]在理想状态下，出错的概率是： 1 M O D \frac{1}{MOD} MOD1
那么全部正确的概率是： ( 1 − 1 M O D ) N (1 - \frac{1}{MOD})^N (1−MOD1)N
代入N=250000 MOD = 1e9+7， 算出概率是：99.975%
看上去很高，只有0.024%+的概率至少出现一个数字出错。
而这是基于假设出错概率 X M O D \frac{X}{MOD} MODX 中X=1的时候，实际情况很难那么理想。
如果X = 250（比较坏的时候，实际我觉得可能是10左右），算出概率就下降很多了：93.941%
这是还没有考虑80多组测试样例的单组正确率。
我们考虑X = 10， 跑50组大样例，正确率：88.25%
所以得双哈希降低出错率。
