← 完整题目索引

PROJECT EULER · #0663

子数组之和

Sums of Subarrays

仅题目 · 已解决原题 ↗

设 tk 为 tribonacci 数,定义为:
t0=t1=0;
t2=1;
tk=tk−1+tk−2+tk−3 for k≥3。

对于给定的整数 n,令 An 为长度为 n 的数组(索引从 0 到 n−1),最初用零填充。
通过在每个步骤中将 An[(t2i−2modn)] 替换为 An[(t2i−2modn)]+2(t2i−1modn)−n+1 i 来迭代更改阵列。
在每个步骤 i 之后,将 Mn(i) 定义为 max{∑j=pqAn[j]:0≤p≤q<n},即 An 的任何连续子数组的最大和。

n=5 的前 6 个步骤如下所示:
初始状态:A5={0,0,0,0,0}
步骤一:⇒A5={−4,0,0,0,0}、M5(1)=0
步骤2:⇒A5={−4,−2,0,0,0}、M5(2)=0
步骤3:⇒A5={−4,−2,4,0,0}、M5(3)=4
步骤4:⇒A5={−4,−2,6,0,0}、M5(4)=6
步骤5:⇒A5={−4,−2,6,0,4}、M5(5)=10
第6步:⇒A5={−4,2,6,0,4}、M5(6)=12

让S(n,l)=∑i=1lMn(i)。因此S(5,6)=32。
您将获得 S(5,100)=2416、S(14,100)=3881 和 S(107,1000)=1618572。

查找 S(10000003,10200000)−S(10000003,10000000)。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。