问题分析 这是一个经典的取石子博弈问题，属于斐波那契博弈的变种。游戏规则如下：

甲先手，第一次取石子数不超过 k 后续每次取石子数不超过上一个人取石子数的 2 倍 必须至少取 1 个石子 ​取走最后一个石子的人失败​（反常规则） 关键思路 ​斐波那契数列的应用​：这类博弈问题通常与斐波那契数列密切相关。当 k=1 时，问题退化为标准的斐波那契博弈。 ​胜负判定​：对于给定的 n 和 k，需要判断甲是否有必胜策略。核心是找到所有使得甲必败的 n（必败态），然后用总数减去必败态的数量。 ​动态规划优化​：由于 k 和 n 的范围极大（最大 10 18 ），直接模拟不可行。代码利用斐波那契数列的性质和记忆化搜索来高效计算。 算法特点 预处理斐波那契数列到第 87 项（足够覆盖 10 18 范围） 使用三维记忆化数组避免重复计算 通过递归分治将大问题分解为斐波那契数列相关的子问题 复杂度分析 预处理：O(1) 每组查询：O(logn) 级别 总复杂度：O(Tlogn)，能够处理 T≤10 5 的大数据量 该算法巧妙地利用了斐波那契博弈的数学性质，将指数级问题转化为对数级解决方案，适用于超大范围的数据输入。