SANSUI'S BLOG

系统外观
分类标签
RSS
Sansui 2023
All rights reserved
人活着就是为了卡卡西

记一道题排列组合题解

11 月 18 日, 2022

难得在网上遇到有认真在做题的人,在此表示深深的感谢。另外个人不太会写题解类的文,权当一个记事了。

题目

题来自 tg 里玩 ai 的小水群,很多人第一眼是想全排列剪枝……阶乘的复杂度得瞎了。

不过看到求方案数,帮人面试时被动态规划虐过的直觉在告诉我,凡事让写方案数不枚举方案的,很可能能写动态规划。

于是从动态规划的方面想去了。

关于素数

这个题有一个非常奇怪的地方,就是要和为素数。我不禁想,和为素数是对解题方法有什么加成吗?

(其实因为我最初看走眼了,以为是子集里所有数为素数,且和为素数,还以为素数和有什么定理)

素数的特殊点在于乘法分解,至于加法上与一般数有什么不同,以凡人视角未曾听说。并且这题还并不限于子集中取用什么数。

综上,和为素数对解题方法不仅没有什么加成,反而是多了个如何判断一个数是不是素数的问题。

至于如何判断素数,在 Leetcode 204,略,也没什么很省时间的方法,就是筛,不算简单。

子集动态规划

既然素数对于解题思路没有加成,就按一般数处理,很快写出了下面的思路:

  1. 一维dp中存下和为当前数的方案数
  2. 遍历更新dp,把新数n拆分成已有数+余数,按余数从大到小(已有数从小到大),把所有已有数的拆分方案加起来,再+1,即可得到当前数的子集数。
    1. 需要注意的是,为了保证不重复,也就是保证子集序列递增,已有数不会超过n/2(余数不会小于n/2)
  3. 更新dp时,也要计算新数n是否为质数,是的话把其子集数加入最终结果(算质数见leetcode 204)
  4. 由于取值范围1-2000,最大和为1000^2,100w,也是dp要遍历的次数。

下面的图是在解释什么叫“遍历但不用枚举子集”时写的,也是上述dp的步骤。

发题人仔细看了,并且手动枚举了10个数后,指出,我这会漏掉10=1+2+3+4。(后面自己发现这样还漏了145和235,后面越漏越多)

仔细回顾了一下之前的思路,发现我的问题出在递增的判断上。我当时认为保证递增序列,只要保证已有数小于余数就行,所以余数>2/n。

但不是的,比如n=10时,已有数为6,余数为4,6拆分为1+2+3就行,1234还是序列递增的。6拆分为2+4、1+5就不行。

归根结底就是我只把余数算了较大的一半,因为余数较大的一半肯定能保证序列递增。如果不想漏情况,余数要全部遍历,但怎么保证序列递增呢?比如6+4,如何只拆到1+2+3+4,不算1+5+4和2+4+4呢?

于是更新了一下递增的条件:

  • 已有数的拆分的子序列最大数小于余数,则拆分方案合法

再更新dp时余数范围:

  • 余数从n取到1,分别计算子集数后再sum。

这样可以保证思路没问题了,但这个“已有数的拆分的子序列最大数小于余数”,明显当前dp只统计了子集数,根本不知道各个子集中具体最大数的情况。因此,我改成了个二维dp,含义和过程如下图:

简单总结一下,整个问题我简化到了求“和为 n 的子集数”,并利用二维动规从 1 求到 n。 n 是不是素数单独算的。

并且发现,其实更新每一行时,都是把上一行为止的方阵以“/”方向45度拆开,mask掉右边部分,按行求和后,从右往左地写进下一行,还能用gpu加个速(不是)。

另一种解法

发题人在看了我的新方案后,说在上面看到了类似杨辉三角之类的东西。并且得出了另一个方案:

和为 n 的子集组合数,为多项式 (x^n+1)(x^(n-1)+1)(x^(n-2)+1)…(x+1) 的 x^n 项系数

(我本来没理解,是死缠烂打地问才知道他在说什么)

仔细一想真的是这个理, x^n 对应的多项式系数就是排列组合到 n 的所有方案数了,也天然没有重复用数的问题。怎么想到的,神。

所以现在问题是:怎么求 (x^n+1)(x^(n-1)+1)(x^(n-2)+1)…(x+1)的多项式系数。

(当时已经不想动脑了,又是死缠烂打地问)

其实迭代就能算,因为 F(n) = x^n • F(n-1) + F(n-1),对应系数直接挪位置后复制粘贴再相加就好了。

空间复杂度

这里有点难以定义 n 具体指哪个,默认 n = 2000 。

我的解法是要 1000^4 的空间去存方案数,矩阵中有很多地方是空的,有点浪费。

后者的解法要1000^2 空间去存多项式系数。省很多。

时间复杂度

以我的动规方法,时间复杂度为在 O(n^6),准确说是O(n^2(n^2+1)(2n^2+1)/6),因为要算到 (n/2)^2,且内部还有已填矩阵按行遍历。

以后者的的解法,时间复杂度为 O(n^3),因为多项式的 n 需要到 (n/2)^2。

线性筛到 (n/2)^2 的素数, 时间复杂度为 O(n^2)。


总得来说还是数学好的强啊。

另外还有一个人非让我看完一个 30 分钟的高斯素数判断法,结果我一直在想 dp,搞得他怨念深重 hh

更新于 2022-11-18 08:00
Waline