← 完整题目索引

PROJECT EULER · #1000

第 1000 题

Problem 1000

仅题目 · 待解原题 ↗

该问题包含三个子问题和一个元问题。输入元问题的答案作为最终答案。

<小时>

子问题:Max And

数字1到n被分为两组A和B。设 I(n) 为 ∑a∈A∑b∈Ba∧b 的最大可能值 其中 ∧ 是按位 AND 运算符。

可以验证 I(10)=50,例如 A={1,4,7,10} 和 B={2,3,5,6,8,9},尽管还有许多其他解决方案。

求 I(1000)。

<小时>

子问题:最大异或和

对于两个整数 x,y,将 x2 和 y2 的按位异或写为 [x,y]。

有限整数序列 a0,a1,…,ar 满足以下属性:

  • 1≤ai≤N 对于所有 0≤i≤r;
  • [ai−1,ai]<[ai,ai+1] 对于所有 0<i<r。

令 X(N) 为总和 ∑i=1r[ai−1,ai] 的最大可能值。

例如,X(4)=71 可以通过序列 2,1,3,2,4,3 来实现。还有 X(10)=702。

求 X(1000)。

<小时>

子问题:无法访问 Nim

两名玩家正在玩三堆 Nim 游戏。游戏状态是一个有序的三元组(a,b,c),代表每堆石子的数量。

玩家总是会做出获胜的举动(如果至少有的话);否则,可以进行任何有效的移动,除非没有剩下有效的移动,此时游戏结束。

如果游戏状态在游戏过程中从未出现,则称为无法到达,除非它处于初始位置。例如,游戏状态(1,1,1)不可达。

令 C(N) 为 0≤a,b,c<N 的不可达状态数。 您将获得 C(10)=123。

求 C(1000)。

<小时>

元问题:

序列 M 定义为

  • M(0)=I(1000);
  • M(1)=X(1000);
  • M(2)=C(1000);
  • M(k)=M(k−1)M(k−2)M(k−3) for k≥3。

您将获得 M(4)≡457587170(mod109+7)。

求 M(1000)mod(109+7)。

提示:我们可以假设 M(4) 的给定值是正确的。

题解待补充

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