记一道题排列组合题解
难得在网上遇到有认真在做题的人，在此表示深深的感谢。另外个人不太会写题解类的文，权当一个记事了。
题目
题来自 tg 里玩 ai 的小水群，很多人第一眼是想全排列剪枝……阶乘的复杂度得瞎了。
不过看到求方案数，帮人面试时被动态规划虐过的直觉在告诉我，凡事让写方案数不枚举方案的，很可能能写动态规划。
于是从动态规划的方面想去了。
关于素数
这个题有一个非常奇怪的地方，就是要和为素数。我不禁想，和为素数是对解题方法有什么加成吗？
（其实因为我最初看走眼了，以为是子集里所有数为素数，且和为素数，还以为素数和有什么定理）
素数的特殊点在于乘法分解，至于加法上与一般数有什么不同，以凡人视角未曾听说。并且这题还并不限于子集中取用什么数。
综上，和为素数对解题方法不仅没有什么加成，反而是多了个如何判断一个数是不是素数的问题。
至于如何判断素数，在 Leetcode 204，略，也没什么很省时间的方法，就是筛，不算简单。
子集动态规划
既然素数对于解题思路没有加成，就按一般数处理，很快写出了下面的思路：
- 一维dp中存下和为当前数的方案数
- 遍历更新dp，把新数n拆分成已有数+余数，按余数从大到小（已有数从小到大），把所有已有数的拆分方案加起来，再+1，即可得到当前数的子集数。
- 需要注意的是，为了保证不重复，也就是保证子集序列递增，已有数不会超过n/2（余数不会小于n/2）
- 更新dp时，也要计算新数n是否为质数，是的话把其子集数加入最终结果（算质数见leetcode 204）
- 由于取值范围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