有人问了一个数论的问题，还和数列有关，挺有意思的，分享给大家。
一、背景
有人问我，如果给一个数列，子数列有多少种？
问：连续吗？有序吗？可以为空吗？
答：非连续、有序、非空。
这个显然是个组合问题。
假设数列长度为 n，则答案显然有2^n - 1
种。
大概思路就是挑1个、挑2个至挑n个。
公式如下：
C(n, 1) + C(n, 2) + ... + C(n, n) = 2^n - 1
然后问题加强了。
如果子数列需要满足序列的值能够整除数列的下标，问序列有多少个？
于是这道题变得有意思了。
二、数据范围
任何问题都要看数据范围。
如果范围比较小，即使是暴力的方法，也是可行的方法。
但是范围大了，就需要找到一种有效的方法了。
比如，这道题的序列总个数有2^n-1
个，n
稍微大一点，暴力的方法就不可接受了。
那具体数据范围是多少呢？
回答：最多有10W
个数字，数字的值在100W
内。
看到10W
意味着这道题的复杂度必须小于O(n^2)
了。
也就是扫描一遍数列后就要求出答案了。
三、第一次分治
既然只能扫描一次就求到答案，那问题就需要拆分了。
原问题：问长度为n
的序列有多少个满足条件的子序列？
第一次拆分：长度为n
的序列中，有多少个满足条件的子序列，是以第i
个数结尾的？
原问题我们记为F(n)
。
第一次拆分我们记为F1(i)
。
显然可以看出，之间的关系下面：
F(n) = F1(1) + F1(2) + ... + F1(n)
如果我们能够分别算出F1(i)
，那最终答案求和就可以计算出来了。
四、第二次拆分
对于F1(i)
，由于第i
个数是子序列的结尾，序列又是有序的（有序，相对前后位置不能改变）。
所以第i
个数之后的数字对于F1(i)
完全无影响。
只有第i
个数之前的数字才会影响F1(i)
。
所以F1(n)
的定义我们可以调整为： 长度为n
的序列中，以最后一个数字为结尾的，满足条件的子序列有多少个？
满足条件？满足的是什么条件呢？
答：子序列的下标能够整除子序列对应下标的值。
也就是满足条件的F1(n)
个子序列的长度，肯定能够被value[n]
整除。
换言之，就是满足条件的子序列的长度肯定是value[n]
的一个约数。
于是这里就可以继续对问题拆分了。
第二次拆分：以vaule[n]
结尾的子序列中，有多少个满足条件的子序列，长度为vaule[n]
的第j
个约数？
第二次拆分后，定义我们称为F2(n, j)
。
假设value[n]
有k
个约数，那么我们可以得到一个等式关系：
F1(n) = F2(n, 1) + F2(n, 2) + ... + F2(n, k)
也就是求出尾数所有约数为长度的满足条件的个数，就求出了尾数满足条件的个数。
五、统计
我们现在的问题是求指定尾数、指定子序列长度、满足条件的个数。
问题具体化，尾数位置为i
，子序列长度为k
。
这样我们就可以把问题转化为：前i-1
个数字中，满足条件的长度为k-1
的个数。
为什么两个是等价的呢？
证明如下： 对于前i-1
个数字中，任何满足长度为k-1
且满足条件的子序列，把第i
个数字追加到子序列最后，依旧满足条件，且长度为k
。
而对于前i-1
个长度不为k-1
的任何子序列，第i
个数字追加上去后，长度不可能为k
。 证明结束。
使用公式就是如下：
F2(n, k)
= stat(n-1, k-1)
而对于stat(n, k)
组成也很容易看出来，一部分包含第n
个数字，一部分不包含。
于是得到下面的公式：
stat(n, k)
= stat(n-1, k) + F2(n, k)
到目前为止，我们公式就彻底形成了闭环，所有的转换都可以使用代码实现了。
六、约数
其实这里对约数计算有讲究的。
一般人计算数字n
的约数个数的时候，直接从1
到n
开始一个一个的尝试能否整除。
这样的复杂度是O(n)
，很多时候是不可接受的。
而对于约数，有一个特征：除了平方数约数，其他的肯定是成对出现的。
所以我们求约数的时候，不需要遍历到n
，而只需要遍历到srqt(n)
即可。
证明也很简单，大家可以自己证明一下。
七、两维数组
在上面推理的时候，出现了两个二维公式F2(n, k)
和stat(n, k)
。
就会有人说这个可能很大，储存不下来怎么办？
这时候我们就需要具体看这两个公式了。
F2(n, k)
= stat(n-1,k-1)
stat(n, k)
= stat(n-1,k) + F2(n,k)
= stat(n-1,k) + stat(n-1,k-1)
看之后有没有发现什么特征？
对于F2(n)
，只与F2(n-1)
有关。
对于stat(n)
只与stat(n-1)
有关。
对于stat(n)
，纯粹依赖于stat(n-1)
，前面的计算后面的，所以使用一个数组从小到大计算就可以了。
而对于stat(k)
，由于用到了stat(k)
和stat(k-1)
，所以对于约数k
我们需要从大到小遍历即可。
为什么可以使用一维代替二维大家可以思考一下。
八、最后
到这里，这个问题我们就完美解决了。
这道题有意思的点在于，组合问题和数论问题结合起来了。
只是不知道有多少人没看懂了
。
后面有时间了，也会多分享一些数论问题和组合问题。
公众号：天空的代码世界
微信：tiankonguse
我是谁：
我是天空，这里有算法、技术、理财、读书、电影、以及一个程序员的生活。谢谢你的阅读。职业上、理财上、生活上，你有问题无法抉择时，都可以加我微信进行交流。
我是观点：
如果你认为这篇文章对你有启发，可以进行一次有深度的思考并留言，也可以带着这个想法转发朋友圈，时间久了，你会发现自己是一个会独立思考的人。
最近文章：
❖ 点赞、留言、分享朋友圈 ❖
❖都是对笔者的一种支持 ❖
点击下方“阅读原文”
