601
# [# 连续整除](# 连续整除)** 连续整除 **
对于任意正整数 n，我们定义函数 streak(n)=k 为使 n+k 不能被 k+1 整除的最小正整数 k。 例如： 13 能被 1 整除 14 能被 2 整除 15 能被 3 整除 16 能被 4 整除 17 不能被 5 整除 因此 streak(13)=4。 类似地： 120 能被 1 整除 121 不能被 2 整除 因此 streak(120)=1。
定义 P(s,N) 为 1<n<N 中满足 streak(n)=s 的整数 n 的数量。 因此 P(3,14)=1，而 P(6,106)=14286。
令 i 取值从 1 到 31，求对应的 P(i,4i) 之和。 602
# [# 抛硬币结果的乘积](# 抛硬币结果的乘积)** 抛硬币结果的乘积 **
爱丽丝正在朋友的帮助下用一枚不公平硬币生成随机数。她和她的朋友围坐在桌子旁，从爱丽丝开始轮流抛掷硬币。每个人都各自记住他们抛出了多少次正面。当爱丽丝抛出正面时，这一流程宣告结束。此时，爱丽丝将她的朋友们所记录的正面次数相乘，作为她的随机数。
举例来说，假如爱丽丝找来鲍勃、查理和道恩帮忙，他们就按照这个顺序坐在桌子旁边，抛掷硬币的结果是序列 THHH—TTTT—THHT—H，从爱丽丝开始并且到爱丽丝结束。鲍勃和查理各自抛出了 2 次正面，而道恩则抛出了 1 次正面。因此爱丽丝的随机数就是 2×2×1=4。
记 e(n,p) 为帮忙的朋友数目为 n（除爱丽丝自己以外）且硬币抛出反面概率为 p 时，爱丽丝所获得的随机数的期望值。
事实上，对于任意固定的 n，e(n,p) 总是 p 的一个多项式。例如 e(3,p)=p3+4p2+p。
定义 c(n,k) 为多项式 e(n,p) 中 pk 项的系数。因此 c(3,1)=1，c(3,2)=4，而 c(3,3)=1。
已知 c(100,40)≡986699437 (mod 109+7)。
求 c(10000000,4000000)mod109+7。 603
# [# 素数拼接的子串和](# 素数拼接的子串和)** 素数拼接的子串和 **
记 S(n) 为整数 n 所能组成的全部连续整数子串的和。从不同位置和顺序得到的相同子串被视为不同的。
例如，S(2024)=2+0+2+4+20+02+24+202+024+2024=2304。
记 P(n) 为将前 n 个素数拼接成的整数。例如，P(7)=2357111317。
记 C(n,k) 为将 k 份 P(n) 拼接成的整数。例如，C(7,3)=235711131723571113172357111317。
# 试计算 S(C(106,1012)) mod (109+7)。 604
# [# 正方形中的凹路径](# 正方形中的凹路径)** 正方形中的凹路径 **
记 F(N) 为，在一个和坐标系对齐的 N×N 正方形中，一个严格凹单调增函数所能够穿过的格点数目最大值。
已知 F(1)=2，F(3)=3，F(9)=6，F(11)=7，F(100)=30 以及 F(50000)=1898。
以下是 N=3 时达成最大值的函数图象：
求 F(1018)。
605
# [# 配对抛掷硬币游戏](# 配对抛掷硬币游戏)** 配对抛掷硬币游戏 **
考虑如下 n 名玩家轮流配对进行的游戏：第 1 轮在玩家 1 和 2 之间进行，第 2 轮在玩家 2 和 3 之间进行，依此类推，直到第 n 轮在玩家 n 和 1 之间进行。然后第 n+1 轮在玩家 1 和 2 之间进行，整个循环重新开始。
换言之，第 r 轮游戏中，玩家 ((r−1)modn)+1 将会面对玩家 (rmodn)+1。
在每一轮中，抛掷一枚公平硬币来决定哪一位玩家赢得本轮。如果有一名玩家同时在第 r 和 r+1 轮获胜，该玩家立即赢得整个游戏。
记 Pn(k) 为玩家 k 在一个 n 名玩家进行的游戏中获胜的概率。例如 P3(1)=12/49，而 P6(2)=368/1323。
记 Mn(k) 为 Pn(k) 表达为最简分数时分子和分母的乘积。例如，M3(1)=588，而 M6(2)=486864。
求 M108+7(104+7) 的最后 8 位数字。
606
# [# 因子链 II](# 因子链 II)** 因子链 II**
n 的因子链指的是一个序列 {1,a,b,…,n}，其中每个元素都整除后一个元素。 例如，12 有八条因子链： {1,12}，{1,2,12}，{1,2,4,12}，{1,2,6,12}，{1,3,12}，{1,3,6,12}，{1,4,12} 和 {1,6,12}。
对于任意 n，将所有不超过于 n 且恰好有 252 条不同因子链的整数 k 的和记为 S(n)。 已知 S(106)=8462952，而 S(1012)=623291998881978。
求 S(1036)，并给出其最后九位数字。
607
# [# 穿越沼泽](# 穿越沼泽)** 穿越沼泽 **
弗罗多和山姆需要从点 A 向东移动 100 里格（长度单位）到达点 B。在普通的土地上，他们每天可以走 10 里格，所以这趟旅程将会花费 10 天时间。但是，他们在路上需要穿过一个从正西南向正东北延伸的长沼泽，而他们在沼泽中行进时需要降低速度。沼泽在任意一处的宽度都是 50 里格，而 AB 连线的中点也恰好落在沼泽的中点。下图展示的是这片区域的地图：
沼泽由 5 个不同的条状部分组成，每个部分宽 10 里格，在地图中表现为深浅的不同。最靠近 A 的条状部分沼泽化程度最浅，在这部分的行进速度可以达到每天 9 里格。然而，随着向东行进，每个条状部分逐渐难以前行，行进速度依次降低为每天 8、7、6 里格，直到最后一部分只有每天 5 里格；随后沼泽部分结束，回到正常的土地上，行进速度恢复到每天 10 里格。
如果弗罗多和山姆径直前往点 B，他们恰好移动 100 里格，而这趟旅程将会花费约 13.4738 天。然而，如果他们不走直路，他们可以缩短旅行所需的时间。
找出从点 A 到点 B 所需的最少旅行时间，以天为单位，并保留小数点后 10 位小数。 608
# [# 因数和](# 因数和)** 因数和 **
记 D(m,n)=∑d|m∑k=1nσ0(kd)，其中 d 取遍 m 的所有因数，而σ0(n) 表示 n 的因数数目。 已知 D(3!,102)=3398 以及 D(4!,106)=268882292。
求 D(200!,1012) mod (109+7)。 609
# [#pi - 序列](#pi - 序列)**π序列 **
对于任意 n≥1，素数计数函数π(n) 表示不超过 n 的素数数目。 例如，π(6)=3 以及π(100)=25。
我们称序列 u=(u0,⋯,um) 为π序列，如果
- 对于任意 n，un≥1
- un+1=π(un)
- u 中包含至少两个元素
对于 u0=10，有三个不同的π序列：(10,4)，(10,4,2) 和 (10,4,2,1)。
记 c(u) 为序列 u 中非素数元素的数目。 记 p(n,k) 为满足 u0≤n 和 c(u)=k 的π序列 u 的数目。 记 P(n) 为所有大于 0 的 p(n,k) 的乘积。 已知：P(10)=3×8×9×3=648 以及 P(100)=31038676032。
求 P(108)，并将答案对 1000000007 取模。 610
# [# 罗马数字 II](# 罗马数字 II)** 罗马数字 II**
一个随机生成器从集合 {I, V, X, L, C, D, M, #} 中生成一个符号序列。序列中的每个符号都是独立于其它符号随机选出的，在每一步中，七个字母都以 14% 的等概率被选中，而 #号则只有 2% 的概率被选中。
我们将生成的符号从左到右地写成序列，直到我们首次碰到 #号出现（但并不写下）。此外，我们还要求写下的字母序列构成一个合法的最简形式罗马数字表示（除非是空序列）。如果写下下一个字母将会违反规则，我们就跳过它，并尝试下一个生成的符号。
请仔细阅读 关于罗马数字 以了解本题中所提及的 “合法罗马数字表示” 和“最简形式”。例如，表示 49 的（唯一）合法序列是 XLIX。减法组合 IL 是不合法的，因为它违反了规则 (ii)，而 XXXXIX 是合法的但不是最简形式。规则中并未限制字母 M 的出现次数，所以所有整数都有一个合法的表示。这些规则同样被用在第 89 题 中，欢迎各位先去解决那道更早的问题。
找出当我们停止时所表示的数的期望值。（当什么都没写下时视为 0。）将答案四舍五入至小数点后 8 位。