python - 最大化平方和模 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

你必须找到最大值((平方和)模 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。