题解：BISHI90 【模板】记忆化搜索 题目链接 递归函数记忆化 题目描述 定义函数 ：  若  或  或 ，则 ； 若  且 ，则 ； 否则，。  给定若干组 （均不超过 ），输出  对  取模的结果。 解题思路  该递归具有大量重叠子问题，且输入上界为 ，可用动态规划自底向上求解。 两种安全实现：  C++ 可直接预处理  至 ； Java/Python 为节省内存，用按  的两层滚动数组：当前层用到同层的  与上一层的 ，可按顺序填表，并在到达某个  时回答对应查询。   实现要点：  将  预处理为 ，，； 按题意套用分支公式，所有加减在模  下进行。    代码   c++   j...

题解：BISHI42 余数求和 题目链接 余数求和 题目描述 给定正整数 ，计算 。 解题思路 将求和拆成两部分：当  时，有 ，贡献为 ；其余  用整除分块： 。令 ，在区间  上  不变，且 ，于是区间贡献为 。 整体复杂度 。 代码   c++   java   python   #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n, k; if (!(cin >> n >&gt...

题解：BISHI41 【模板】整除分块 题目链接 【模板】整除分块 题目描述 给定正整数 ，求表达式  的值。 解题思路 直接求和是 ，不可行。利用“整除分块”，当  处于一个区间内时， 取值相同。设 ，则该  维持不变的最大右端点为 。于是把区间  一次性贡献： ，再令  继续。 该做法步数为不同商的个数，约为 。 代码   c++   java   python   #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); l...

题解：BISHI40 数组取精 题目链接 数组取精 题目描述 给定两个长度为  的正整数序列  与 。 定义子集 （，元素互异）为“精华子集”，当且仅当同时满足：     请构造任意一个满足条件的精华子集并输出其大小及下标。 解题思路 分块配对 + 贪心：  将下标按  降序排序为 ，并将其两两配成区间对 。 设 ，维护当前选中和 。 依次处理每一对 ：分别试选  或 ，比较二者对“剩余缺口” 的降低量，取更优者；若相同，优先增大较大缺口的那一维。 若  为奇数，末尾还会有一个单点，直接加入。  这样在每个配对块上都做出对两维半和同时有利的选择，最终得到  的集合，且两维均严格大于全体的一半。...

题解：BISHI39 【模板】Pollard-Pho算法 题目链接 【模板】Pollard-Pho算法（素数判定） 题目描述 给定  组询问，每次给出一个正整数 ，判断  是否为质数。 可能较大。 解题思路 本题仅需素性测试，用 Miller–Rabin（米勒拉宾）随机化判定的确定化基即可在  位范围内常数时间判素：  将  写成 ，任选若干底数 ，计算 ；若  则当前底数通过；否则反复平方  次，若出现  则通过，否则判合数。 对于 ，底数集合  已足以确定化。  如需进一步做分解，可在此基础上加入 Pollard–Rho，但本题不需要分解，仅判素即可。 代码   c++   java   ...

题解：BISHI38 有向二分图构造 题目链接 有向二分图构造 题目描述 给定一张有向图，含  个点与  条有向边。需要给每个点染成黑或白两色。若一条边的起点为黑色、终点为白色，则称其为“核心边”。请构造一种染色方案，使得核心边的条数不少于 ，并输出你构造方案下所有核心边的编号（按输入顺序从  到  编号）。保证至少存在一种可行解。 解题思路 随机将每个点独立地以  概率染黑 / 染白时，任意一条边成为“黑  白”的概率是 ，因此核心边条数的期望为 ，从而存在一份染色使核心边不少于 。我们用“条件期望法”进行完全去随机化，线性时间即可构造：  设当前已为部分点定色，其余点未定。对一个未定点 ：...

题解：BISHI37 数位差与数值和的构造 题目链接 数位差与数值和的构造 题目描述 给定整数 ，请构造非负整数 ，满足 ，且 ，其中  表示  的十进制各位数字之和。保证解一定存在。 解题思路 目标是让  与  的数位和尽量均衡，同时保证逐位相加无进位，从而自然满足 。设  的十进制从高到低的每一位为 ：  若  为偶数，则把该位平均分给 ，即本位  取 ， 取 ； 若  为奇数，则在本位让  与  在  之间交替分配（用一个开关在遇到奇数位时翻转）。  由于对每一位都保证两数本位之和等于 ，故整个加法无进位，天然满足 ；而所有奇数位多出来的那个  会在  之间交替分担，因而两者的数位和之差...

题解：BISHI36 【模板】扩展巴什博弈 题目链接 【模板】扩展巴什博弈 题目描述 有一堆石子，双方轮流取走石子。设初始石子数为 ，每次必须取走  到  颗（含端点）。若某时刻剩余石子少于  则无法行动，该玩家失败；拿到最后一颗者获胜。给出多组 ，判断先手是否必胜（YES/NO）。 解题思路 经典扩展巴什博弈（取走区间 ）。记  为先手在  时是否必胜。可得败态呈现周期性：  结论：先手必败当且仅当 ；否则先手必胜。  证明要点（简述）：将非负整数按长度为  的“败段”和长度为  的“胜段”交替划分，周期为 。处于败段时，所有可达状态（减去  中任意值）都落在后续的胜段；处于胜段时，总能选择...

题解：BISHI35 【模板】巴什博弈 题目链接 【模板】巴什博弈 题目描述 有一堆石子，双方轮流取走石子。设初始石子数为 ，每次可以取走  到  颗（即至多  颗），拿到最后一个石子者获胜。给出多组数据 ，判断先手是否必胜，输出 YES/NO。 解题思路 经典巴什博弈。关键在于把局面维持在  的倍数：  若 ，则无论先手取 ，都会留给后手  的必胜态； 若 ，先手一次取 （且 ），把局面送到  的倍数，之后先手始终“对称”到 ，最终拿到最后一颗。  结论：先手必胜当且仅当 。 代码   c++   java   python   #include <bits/stdc++.h> ...

题解：BISHI34 甜蜜的博弈 题目链接 甜蜜的博弈 题目描述 有一堆钻石，进行如下回合制游戏：Alice 先手、Bob 后手，双方轮流操作。设当前剩余钻石数量为 。每回合玩家可按题面给出的三种合法方式之一移除若干颗钻石（其中包含“移除  颗”和“移除  颗”的选项）。当某位玩家无法进行操作时，该玩家失败。给定  组询问，每组给定初始 ，若双方最优博弈，判断胜者（输出 Alice 或 Bob）。 样例：当  输出 Alice；当  输出 Bob；当  输出 Alice。 解题思路 这是一个依赖状态的减法博弈。设  表示先手在剩余  颗时是否必胜。可行动作：  任意 ，可取 ； 若  为偶数且...

题解：BISHI36 【模板】扩展巴什博弈   题目链接   【模板】扩展巴什博弈   题目描述   有一堆石子，双方轮流取走石子。设初始石子数为 ，每次必须取走 到 颗（含端点）。若某时刻剩余石子少于 则无法行动，该玩家失败；拿到最后一颗者获胜。给出多组 ，判断先手是否必胜（YES/NO）。   解题思路   经典扩展巴什博弈（取走区间 ）。记 为先手在 时是否必胜。可得败态呈现周期性：    结论：先手必败当且仅当 ；否则先手必胜。    证明要点（简述）：将非负整数按长度为 的“败段”和长度为 的“胜段”交替划分，周期为 。处于败段时，所有可达状态（减去 中任意值）都落在后续的胜段；处于...

验题人个人题解，写了除数论外的十二题。本文中不会讲述前置知识，默认大家都会，并且不会写详细的思考过程，请大家多多思考。 按个人体感难度顺序递增。 K 签到1  前置知识点：模拟  简单模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202082 L 签到2  前置知识点：stl  stl模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202091 E 传送门  前置知识点:bfs/di...

验题人个人题解，写了除数论外的十二题。本文中不会讲述前置知识，默认大家都会，并且不会写详细的思考过程，请大家多多思考。 按个人体感难度顺序递增。 K 签到1  前置知识点：模拟  简单模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202082 L 签到2  前置知识点：stl  stl模拟 略 代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=76202091 E 传送门  前置知识点:bfs/di...