Member 14793179 Ответов: 2

Суммирование мощности K абсолютного значения разности каждой пары массивов


В основном f(x) - это суммирование степени K абсолютного значения разности каждой пары массивов.В этом вопросе будут даны n(количество элементов в массиве),k и элемент,и я должен сначала оштрафовать абсолютную разницу между каждой парой массива и поднять ее мощность k, затем сложить их все и найти ответ%pow(10,9)+7

Что я уже пробовал:

Я попробовал эту проблему , используя 3 петли, одну для питания. потому что значение k может быть доведено до 100000,а элемент массива-до 10^9

k5054

Может быть, вы можете опубликовать точную проблему, которую пытаетесь решить? Как уже было сказано, казалось бы, что вы должны быть в состоянии вычислить значения в с величиной порядка 1E+900000. Это значение слишком велико даже для длинного двойника в 64 бита, который был бы порядка 1E+4932, поэтому должны быть какие-то другие ограничения на эту проблему, или вы должны использовать библиотеку bignum для вычисления значений.
Тем не менее, вы также должны опубликовать свой код. Мы очень рады рассмотреть ваше решение и предложить исправления, но мы не предоставляем решения напрямую.

2 Ответов

Рейтинг:
1

Member 14793221

попытка обмануть э-э (паучья неделя кода Нитта)


Рейтинг:
0

Member 14794342

Вместо того чтобы использовать три цикла со сложностью O(n^3), Вы можете использовать модульное возведение в степень в качестве третьего цикла, который займет O(log n) для вычисления мощности k для разности каждой пары массива.
Я хочу добавить в этот вопрос, как мы можем вычислить суммирование разностей каждой пары, поднятой до степени k менее чем за O(n^2 log n).