扩治法解决NPC问题
对于一个NPC问题，至今也没有人能够给出多项式时间解法，然而今天我发现了一种基于全新算法的多项式时间解法。
一、算法引入
对于一个复杂问题，有一种传统的方法是进行分治(Divide and Conquer)，即将大问题划分为多个小问题分别解决，然而这种方法在处理NPC问题时并没有什么用处。
在阅读大量文献资料后，我在古人的文章中找到了答案：
得其大者可以兼其小。 —— 欧阳修《易或问》
原来我们的思维被局限在了将问题简化处理，于是一种新的算法呼之欲出——扩治(Broaden and Conquer)，我们可以考虑递归扩大（或转换）问题，每次处理出与扩大（或转换）后的一个或多个问题到原问题的转移，最后统计出答案。
二、复杂度证明
很多人可能会觉得这个复杂度显然错误，甚至不可能在有限时间内求出答案，但我想告诉你，这是因为你被局限在了思维定式中。
在又查阅大量文献资料后，我发现了这篇文章，此文在困难的A+B Problem中运用了扩治的思想实现了极其优秀的复杂度，甚至给出了严谨的复杂度证明，这启发了我们的解决。
举个例子吧，如哈密顿路径，即判断n个点的图是否存在恰好经过每个点一次的路径。
对于一个n个点的图
- 如果它存在哈密顿路径，那么在这条路径的起点前添加一个n个点的链（将链的终点与原图的起点相连），这个2n个点的图的哈密顿路径存在性显然与原图相同，所以我们可以直接暴力每个点为起点。
- 如果它不存在哈密顿路径，那么添加链的操作也不会改变其哈密顿路径存在性。
至此，我们完成了一步扩治，递归这个步骤即可。
现在计算复杂度（以下均讨论最差复杂度），我们设n个点问题的复杂度为
每层扩治添加链的复杂度为
移项得：
化简得：
即：
经过推导（太菜了不会，只能问DeepSeek），复杂度约为
三、杂谈
扩治算法在OI中应用前景一片光明，不仅拥有极为优秀的复杂度，还能解决许多本来几乎无解的问题，应该被发扬光大！
所以什么时候给我发诺贝尔信息奖?