考虑由以下伪随机数生成器生成的整数序列： $$S_0=290707, \quad S_{n+1}=S_n^2 \bmod 50515093.$$ 记$A(i, j)$为$S_i, S_{i+1}, \ldots, S_j$中的最小值，并记$M(N)=\sum_{1\le i\le j\le N}A(i,j)$。

可以验证$M(10)=432256955$以及$M(10000)=3264567774119$。

求$M(2\times 10^9)$。

本题难度:

解答

容易验证，$S_n$是周期为6308948的周期序列。

对每一个$S_i$，分别找到其左边第一个比它小的数$L_i$和右边第一个比它小的数的下标$R_i$，那么$S_i$是其中任意子区间的最小值，这样的区间共有$(R_i-i)(i-L_i)$个。

把所有$2\times 10^9$项按T分块后计算即可得结果$7435327983715286168$。

Q=2000000000
T=6308948
mod=50515093

S=[0]*T
S[0]=(290797*290797)%mod
for i in range(1,T):
    S[i]=(S[i-1]*S[i-1])%mod

res=Q*(Q+1)//2
ans=0

r=Q%T
m=2*T+r

L=[0]*m
R=[0]*m

st=[]
for i in range(m):
    while st and S[i%T] < S[st[-1]%T]:
        st.pop()
    L[i]=0 if not st else st[-1]+1
    st.append(i)

st=[]
for i in range(m-1,-1,-1):
    while st and S[i%T] < S[st[-1]%T]:
        st.pop()
    R[i]=m-1 if not st else st[-1]-1
    st.append(i)

for i in range(T):
    tmp=(i-L[i]+1)*(R[i]-i+1)
    ans+=tmp*S[i]
    res-=tmp
    j=2*T+r-1-i
    tmp=(j-L[j]+1)*(R[j]-j+1)
    ans+=tmp*S[j%T]
    res-=tmp
    tmp=(i+T-L[i+T]+1)*(R[i]-i+1)
    c=Q//T-2+(i < r)
    ans+=tmp*S[i]*c
    res-=tmp*c

ans+=res*min(S)

print ans