最大化模 m 平方和的代码

Question

输入：

k-> number of lists
m->modulo
Constraints
1<=k<=7
1<=M<=1000
1<=Magnitude of elements in list<=10*9
1<=Elements in each list<=7
` 

这段代码负责最大化从列表(x1^2 + x2^2 + ...) % m中x1, x2, ...选择的位置X1, X2, ...

k,m=map(int,input().split())
Sum=0
s=[]
for _ in range(k):
    s.append(max(map(int,input().split())))
    Sum+=int(s[_])**2
print(Sum%m)

例如，如果输入是：

3 1000
2 5 4
3 7 8 9 
5 5 7 8 9 10 

输出将为 206，因为选择每个列表中的最高元素，对该元素求平方，求和并使用以下命令执行模运算m

所以，那就是(5^2+9^2+10^2)%1000=206

如果我提供类似的输入，

3 998
6 67828645 425092764 242723908 669696211 501122842 438815206
4 625649397 295060482 262686951 815352670
3 100876777 196900030 523615865

预期的输出是974，但我得到624

我想知道您将如何解决这个问题或如何更正现有代码。

Answer 1

您必须找到 max((平方和) 模 m)。这与 max(平方和) 模 m 不同。

您可能会发现平方和的绝对值并不是尽可能大，但是当您对 m 取模时平方和最大。

例如：

m=100
[10, 9],
[10, 5]

此处，最大平方和为 100 + 100 = 200，即 0 模 100。最大值（平方和模 100）为 (81 + 100) = 182，即 82 模 100。

鉴于 m 被迫很小，有一个快速动态编程解决方案可以在 O(m * N) 时间内运行，其中 N 是所有列表中的项目总数。

def solve(m, xxs):
    r = [1] + [0] * (m - 1)
    for xs in xxs:
        s = [0] * m
        for i in xrange(m):
            for x in xs:
                xx = (x * x) % m
                s[i] += r[(i - xx) % m]
        r = s
    return max(i for i in xrange(m) if r[i])

m = 998
xxs = [
    [67828645, 425092764, 242723908, 669696211, 501122842, 438815206],
    [625649397, 295060482, 262686951, 815352670],
    [100876777, 196900030, 523615865]]

print solve(m, xxs)

这样974就可以按要求输出了。