我有N个整数,例如3,1,4,5,2,8,7.可能有一些重复.我想将这个序列分成连续的子序列,这样我们就可以从它们形成非递减序列.如何计算最小数量的削减？对于上面提到的示例,答案是6,因为我们可以将此序列划分为{3},{1},{4,5},{2},{7},{8},然后形成{1,2 ,3,4,5,7,8}.最快的方法是什么？
假设某些数字可能相等,有谁知道如何解决它？
我想计算给定$ N $元素集的每个子集的乘积之和.例如,给定集合{1,2,3},答案是1 + 2 + 3 + 1*2 + 1*3 + 2*3 + 1*2*3.我还想给出模数$ $ M $.
我所知道的是我可以计算$(x - a_1)(x - a_2)...(x - a_n) - 1 $,但这会涉及FFT,因此可能存在一些舍入误差,但主要问题是这个想法是需要$ O(N\log ^ 2 N)$时间并且模数$ M $是有问题的.有没有更快的方法来解决这个问题？这不是我的功课,我从老师那里得到了这个任务来练习编程比赛,但我真的遇到了这个问题.
约束:
$ a_i\le 10 ^ 9 $
$ N\le 10 ^ 6 $
$ M\le 10 ^ 9 $
我有两个非负整数 x 和 y，它们都最多有 30 位（所以它们的值约为 10^9）。
我想计算有多少组 4 个数字 {a_1, a_2, a_3, a_4} 使得 a_1 + a_2 = x 和 a_3 + a_4 = y 并且所有这 4 个数字的异或等于 0。
解决这个问题最快的算法是什么？
我能想到的最快的方法是将异或方程重新排列为a_1 xor a_2 = a_3 xor a_4。
然后我可以在 O(x) 中计算左侧的所有值，在 O(y) 中计算右侧的所有值，因此整个算法在 O(x + y) 中运行。