聊聊数论与数列的一个问题

一、背景

有人问我，如果给一个数列，子数列有多少种？
问：连续吗？有序吗？可以为空吗？ 答：非连续、有序、非空。

这个显然是个组合问题。 假设数列长度为 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我们需要从大到小遍历即可。
为什么大家可以思考一下。

八、最后

到这里，这个问题我们就完美解决了。
这道题有意思的点在于，组合问题和数论问题结合起来了。
后面有时间了，也会多分享一些数论问题和组合问题。

-end-