循环不变式
WeLikeStudying · · 题解
简介
- 循环不变式是一种较好的设计算法的方法之一,也是我们开发算法前期必须掌握的方法。
- 它的主要思想是为了达到某个目的,在每次循环同时维护一个性质,在循环结束的时后,达到目标性质。
- 与我们小学,初中,高中接触的常见思想:将问题分为与原问题等价但规模更小的子问题(子问题不重叠的我们称作分治,子问题大量重叠的我们称之为动态规划)不同,在求解问题中,我们的实际在求解一连串的相似但不尽相同的问题。
- 在大学教材中,许多基础算法的严格证明都运用了循环不变式,想必大家早已认识到它的重要性。
- 今天我们以一道典型题目为例子,讲解如何使用循环不变式设计算法。
例题
- 我们来一道例题狄利克雷卷积。
-
$$b_k=\sum_{i|k}a_i$$ -
思路
- 直接的做法复杂度是调和级数的
\Theta(n\ln n) ,显然无法通过本题。 - 但是,仔细看一下,以下是
n=10 的情况: - 即使我是瞎点的也可以看出这里面重复颇多,这为我们的优化提供了启示。
- 还有一个有趣的事情,这一题我们我们有一个现成的范本:埃拉托斯特尼筛法,它以从小到大的顺序逐个给出了每个数的质因子,而且其本身的时间复杂度之前已有讨论,是
\Theta(n\ln\ln n) 的。 - 我们将以该算法为外壳,设计求解该问题的算法。
设计循环不变式
- 设计什么样的循环不变式呢?
- 循环不变式的三个步骤:初始状态,中间状态,结束状态,其中初始状态和结束状态是中间状态的特殊情况。
- 可以看出,基本的要求是:和质因子有关的,结果满足
b_k=\sum_{i|k}a_i 的。 - 我们可能一开始会设计出这样的循环不变式:当处理完
p_i (第i 个质数)时,b_k 所累加的a 数组和的下标i 是所有满足i|k 且i 的唯一因子分解(规定如果是质数唯一因子分解是它本身,1 的唯一因子分解为空)中只包含p_1,p_2,\cdots p_i ,初始状态是b_k=a_1 。 - 这个循环不变式是难以维护的。(想一想,为什么)
- 较好的循环不变式是:当处理完
p_i (第i 个质数)时,b_k 所累加的a 数组和的下标j 是所有满足j|k 且\frac kj 的唯一因子分解中只包含p_1,p_2,\cdots p_i 的,初始状态是b_k=a_k 。
维护循环不变式
- 我们选择这样的循环不变式当然是因为它容易维护。
- 我们约定枚举完
p_i 后的b_k 数组的值为b_k^{(i)} 以便讲解(特别地b_k^{(0)}=a_k )。 - 考虑在枚举
p_i 的时候,我们让b_k 的值由b_k^{(i-1)} 变为b_k^{(i)} 。 - 考虑
b_k^{(i)}-b_k^{(i-1)} ,可以发现它是:当处理完p_i (第i 个质数)时,b_k 所累加的a 数组和的下标j 是所有满足j|k 且\frac kj 的唯一因子分解中只包含p_1,p_2,\cdots p_{(i-1)} 且一定有p_i 的,也就是\frac k{j\cdot p_i} 的唯一因子分解中只包含p_1,p_2,\cdots p_i 的,即b_{k/p_i}^{(i)} 。 - 可以发现我们如果按顺序执行埃氏筛法就可以保证
b_{k/p_i}=b_{k/p_i}^{(i)} 。(想一想,为什么) - 于是整个算法也可以确定下来了:时间复杂度
\Theta(n\ln\ln n) ,空间复杂度\Theta(n) ,可以通过例题。
代码实现
#include<fstream>
#define uint unsigned int
const uint MAXN=2e7+1;
using namespace std;
uint n,seed,b[MAXN],ans=0;
bool np[MAXN];
inline uint getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
int main()
{
scanf("%u%u",&n,&seed);
for(int i=1;i<=n;++i)b[i]=getnext();
np[1]=1;
for(int i=1;i<=n;++i)
{
if(!np[i])
for(int j=1;i*j<=n;++j)
b[i*j]+=b[j],np[i*j]=1;
ans^=b[i];
}
printf("%u",ans);
return 0;
}
总结
- 循环不变式的确是一种巧妙的办法,我们在实际解决问题的时候,要从多角度思考,灵活解决问题。
课后习题
- 思考:如果
b_k 的推导分别是以下的两个式子,我们之前设计的算法还可行吗?b_k=\sum_{i=1}^na_{\lfloor\frac ki\rfloor} b_k=a_k+\sum_{d|k,d\ne k}b_d
习题答案
感谢 @kintsgi 的提醒,我已经将两道习题变成了可以评测的形式,大家如果有兴趣可以去提交。
- 课后习题 1
- 课后习题 2
如果你不会做,我可以提供提示,往下看吧。
提示
目标复杂度都是