我们可以使用动态编程来解决这个问题吗

Question

查找大小为n的子序列的数量，求和使得取模m后，和变得大于或等于x。
其中：
1<=n<=42
1<=m<=10^9
0<=x<m
如何解决此问题

Answer 1

使用名为"在中间相遇"；。正如Peter de Rivaz建议的那样，你可以将你的输入分为两组A和B，每组21个或更少的元素。

步骤1:
A中有2^|A|个元素组合，针对每个元素计算总和mod m并将其存储在表T中。对表T进行排序。

步骤2：
对于B元素的2^|B|组合中的每个组合c，计算c mod m的和s。现在，您可以确定范围i->j s.t.s + i >= x mod m，在T上使用二进制搜索，可以确定t在所需范围内的表条目数。

它的运行时间是O(2^{n/2}*n(，对于n=42，它是可计算的。