用“Blum Blum Shub”伪随机数生成算法按如下方式生成数字序列： $$s_0=14025256 \quad s_{n+1}=s_n^2 \bmod 20300713.$$ 将这些数$s_0,s_1,s_2,\ldots$连接起来形成一个无穷长的字符串$w=14025256741014958470038053646\ldots$

给定自然数k，若w中不存在和为k的子串，则$p(k)=0$。否则$p(k)=z$，其中z是首个和为k的子串的起始下标（下标从1开始）。

例如子串$1, 14, 1402, \ldots$的和分别是 $1, 5, 7, \ldots$且开始位置均为1，因此$p(1)=p(5)=p(7)=\ldots=1$。

子串$4, 402, 4025, \ldots$的各位数字和分别是$4, 6, 11, \ldots$且开始位置均为2，因此$p(4)=p(6)=p(11)=…=2$。

子串$02, 0252, \ldots$的各位数字和分别是$2, 9, \ldots$，且开始位置均为3，因此$p(2)=p(9)=…=3$。

注意开始位置为3的子串025的各位数字和是7，但1402出现得更早，因此$p(7)=1$，而非3。

可以验证，$\sum_{k=1}^{1000}p(k)=4742$，求$\sum_{k=1}^{2\times 10^{15}}p(k)$。

本题难度:

解答

本题除了穷举外没有太好的策略，但数据量很大不易调试。

由定义容易看出s必定是周期序列，简单试算即可发现周期是2534198，一个周期内所有数字之和是80846691。

生成略多于一个周期的所有数位（此处选择增加100位），这样做的原因是存在一些小于80846691的数值k是由跨越两个周期的子列之和所得。

接下来依次枚举左端点，对每个左端点，不断向右求和。

此处唯一的优化是在每次确定左端点后先更新求和的上限，设从左端点到末尾的和为t，若$p(t),p(t-1),\ldots,p(t-k)$已经在此前的步骤中计算出来，则显然只需求和至t-k-1即可。

引入此优化后只需枚举100次左端点，最终的结果是$9922545104535661$。

注：因本题计算量较大，代码中打印了进度信息。

M=2*(10**15)
X=80846691

m1=M/X
m2=M%X

s=14025256
d=[]
p=[0]*80846692
k=t=r=rr=0
while k==0 or s!=14025256:
    for c in str(s):
        d.append(int(c))
        t+=d[-1]
        if p[t]==0:
            p[t]=1
            r+=(m1+(t <= m2 and t!=X))
    s=(s*s)%20300713
    k+=1

d+=d[:100]
t+=sum(d[:100])


a=1
b=t
while a < len(d) and b>0:
    if d[a-1]>0:
        b=min(b,t)
        while b>0 and b < len(p) and p[b]>0:
            b-=1
        if b>0:
            i=a
            z=0
            while i < len(d) and z+d[i] <= b:
                z+=d[i]
                if z < len(p) and z>0 and p[z]==0:
                    p[z]=a+1
                    r+=(a+1)*(m1+(z <= m2 and z!=X))
                i+=1
    print a,b
    t-=d[a]
    a+=1

print r