Задача подсчета сумм, слагаемых, которые являются числами с even number of ones in bin, и каждое число, поднятое до степени 4. Проблема в том, что последнее слагаемое равно 2 , поэтому обычный расчет занимает много времени. Я думаю, что здесь может помочь динамическое программирование, но я не могу понять, как его использовать здесь.
Вот пример:
Подсчет суммы с большим количеством слагаемых
Пожалуйста, может кто-нибудь помочь мне с этой проблемой?
Там в formula to calculate the sum of the powers of 4 of all integers from 1 to n:
сумма (K) = к < = п = (6 * п + 15 * N + 10 * N - n)/30
В вашей проблеме вы должны суммировать только силы 4 из k, которые имеют четное число единиц в их двоичном представлении. И эта формула не исключает k с нечетным числом единиц.
Однако мое чувство кишки говорит мне, что сумма степеней 4 из k, имеющих нечетное число единиц, должна быть примерно такой же, как сумма степеней 4 из k с четным числом единиц.
Оказывается, что если подсчитать эти две суммы для ряда Д.К., эти суммы будут точно так же раз в то время, когда в каждом 32 Д.К.:
n= 0 OddSum= 0 EvenSum= 0 = =
n= 1 OddSum= 1 EvenSum= 0
n= 2 OddSum= 17 EvenSum= 0
n= 3 OddSum= 17 EvenSum= 81
n= 4 OddSum= 273 EvenSum= 81
n= 5 OddSum= 273 EvenSum= 706
n= 6 OddSum= 273 EvenSum= 2002
n= 7 OddSum= 2674 EvenSum= 2002
n= 8 OddSum= 6770 EvenSum= 2002
n= 9 OddSum= 6770 EvenSum= 8563
n= 10 OddSum= 6770 EvenSum= 18563
n= 11 OddSum= 21411 EvenSum= 18563
n= 12 OddSum= 21411 EvenSum= 39299
n= 13 OddSum= 49972 EvenSum= 39299
n= 14 OddSum= 88388 EvenSum= 39299
n= 15 OddSum= 88388 EvenSum= 89924
n= 16 OddSum= 153924 EvenSum= 89924
n= 17 OddSum= 153924 EvenSum= 173445
n= 18 OddSum= 153924 EvenSum= 278421
n= 19 OddSum= 284245 EvenSum= 278421
n= 20 OddSum= 284245 EvenSum= 438421
n= 21 OddSum= 478726 EvenSum= 438421
n= 22 OddSum= 712982 EvenSum= 438421
n= 23 OddSum= 712982 EvenSum= 718262
n= 24 OddSum= 712982 EvenSum= 1050038
n= 25 OddSum= 1103607 EvenSum= 1050038
n= 26 OddSum= 1560583 EvenSum= 1050038
n= 27 OddSum= 1560583 EvenSum= 1581479
n= 28 OddSum= 2175239 EvenSum= 1581479
n= 29 OddSum= 2175239 EvenSum= 2288760
n= 30 OddSum= 2175239 EvenSum= 3098760
n= 31 OddSum= 3098760 EvenSum= 3098760 = =
n= 32 OddSum= 4147336 EvenSum= 3098760
n= 33 OddSum= 4147336 EvenSum= 4284681
n= 34 OddSum= 4147336 EvenSum= 5621017
n= 35 OddSum= 5647961 EvenSum= 5621017
n= 36 OddSum= 5647961 EvenSum= 7300633
n= 37 OddSum= 7522122 EvenSum= 7300633
n= 38 OddSum= 9607258 EvenSum= 7300633
n= 39 OddSum= 9607258 EvenSum= 9614074
n= 40 OddSum= 9607258 EvenSum= 12174074
n= 41 OddSum= 12433019 EvenSum= 12174074
n= 42 OddSum= 15544715 EvenSum= 12174074
n= 43 OddSum= 15544715 EvenSum= 15592875
n= 44 OddSum= 19292811 EvenSum= 15592875
n= 45 OddSum= 19292811 EvenSum= 19693500
n= 46 OddSum= 19292811 EvenSum= 24170956
n= 47 OddSum= 24172492 EvenSum= 24170956
n= 48 OddSum= 24172492 EvenSum= 29479372
n= 49 OddSum= 29937293 EvenSum= 29479372
n= 50 OddSum= 36187293 EvenSum= 29479372
n= 51 OddSum= 36187293 EvenSum= 36244573
n= 52 OddSum= 43498909 EvenSum= 36244573
n= 53 OddSum= 43498909 EvenSum= 44135054
n= 54 OddSum= 43498909 EvenSum= 52638110
n= 55 OddSum= 52649534 EvenSum= 52638110
n= 56 OddSum= 62484030 EvenSum= 52638110
n= 57 OddSum= 62484030 EvenSum= 63194111
n= 58 OddSum= 62484030 EvenSum= 74510607
n= 59 OddSum= 74601391 EvenSum= 74510607
n= 60 OddSum= 74601391 EvenSum= 87470607
n= 61 OddSum= 88447232 EvenSum= 87470607
n= 62 OddSum= 103223568 EvenSum= 87470607
n= 63 OddSum= 103223568 EvenSum= 103223568 = =
n= 64 OddSum= 120000784 EvenSum= 103223568
...
n=4062 OddSum= 110517674755433207 EvenSum= 110790187795938168
n=4063 OddSum= 110790187795938168 EvenSum= 110790187795938168 = =
n=4064 OddSum= 111062969223019384 EvenSum= 110790187795938168
n=4065 OddSum= 111062969223019384 EvenSum= 111063237807788793
n=4066 OddSum= 111062969223019384 EvenSum= 111336556602699529
n=4067 OddSum= 111336556999378505 EvenSum= 111336556602699529
n=4068 OddSum= 111336556999378505 EvenSum= 111610413558992905
n=4069 OddSum= 111610683334189626 EvenSum= 111610413558992905
n=4070 OddSum= 111885079246199626 EvenSum= 111610413558992905
n=4071 OddSum= 111885079246199626 EvenSum= 111885079246980586
n=4072 OddSum= 111885079246199626 EvenSum= 112160014909822442
n=4073 OddSum= 112160285082869867 EvenSum= 112160014909822442
n=4074 OddSum= 112435761292440443 EvenSum= 112160014909822442
n=4075 OddSum= 112435761292440443 EvenSum= 112435761691463067
n=4076 OddSum= 112711778845418619 EvenSum= 112435761691463067
n=4077 OddSum= 112711778845418619 EvenSum= 112712050215144108
n=4078 OddSum= 112711778845418619 EvenSum= 112988609908991164
n=4079 OddSum= 112988609908992700 EvenSum= 112988609908991164
n=4080 OddSum= 112988609908992700 EvenSum= 113265712541951164
n=4081 OddSum= 113265984311095421 EvenSum= 113265712541951164
n=4082 OddSum= 113543630682195597 EvenSum= 113265712541951164
n=4083 OddSum= 113543630682195597 EvenSum= 113543631082001485
n=4084 OddSum= 113821821591246733 EvenSum= 113543631082001485
n=4085 OddSum= 113821821591246733 EvenSum= 113822094560202110
n=4086 OddSum= 113821821591246733 EvenSum= 114100830807798926
n=4087 OddSum= 114100830808584494 EvenSum= 114100830807798926
n=4088 OddSum= 114380113196106030 EvenSum= 114100830807798926
n=4089 OddSum= 114380113196106030 EvenSum= 114380386566045167
n=4090 OddSum= 114380113196106030 EvenSum= 114660215895655167
n=4091 OddSum= 114660216297816991 EvenSum= 114660215895655167
n=4092 OddSum= 114660216297816991 EvenSum= 114940592970302463
n=4093 OddSum= 114940867546334192 EvenSum= 114940592970302463
n=4094 OddSum= 115221793169753088 EvenSum= 114940592970302463
n=4095 OddSum= 115221793169753088 EvenSum= 115221793169753088 = =
...
Без формального доказательства я предполагают, что ответ, следовательно, является:
((6 * п + 15 * п + 10 * п - п)/30)/2
где n = 2 -1.
Если я понял это правильно, «n» обозначает количество бит? Поэтому для каждой строки в вашей таблице нечетная сумма представляет собой сумму четвертых степеней всех n-битовых чисел с нечетной четностью; и четную сумму, которая для n-разрядных чисел с четной четностью? Если мое понимание правильное, первая ошибка в таблице равна n = 2, где четная сумма должна быть 81 (11 двоичных = 3 десятичных, 3^4 = 81). Таблица также неверна в ряде других мест, где четная сумма для трех последовательных значений n одинакова (например, n = 24,25,26). Если я неправильно понял, пожалуйста, уточните. Помимо этой проблемы, мне нравится ответ. –
'n' - максимальное число, которое мы поднимаем до степени 4 в сумме. В постановке задачи она идет от 0 до 3 до 5, 6, 9, 10, 12, 15, ..., 2^64-1. Делайте суммы степеней 4 чисел с нечетным и четным количеством единиц вручную для небольших чисел, чтобы увидеть, что находится в таблице. Моя таблица точно воспроизводит суммы степеней 4 чисел с четным числом единиц. «Одиночки» существуют, потому что следующий «n» вносит вклад в «нечетную» сумму или в «четную» сумму, но не в обоих, поскольку «n» не может иметь четное и нечетное число одновременно. –
Я поддержал, потому что вы предложили использовать математику, чтобы придумать решение с закрытой формой (постоянное время!) Вместо вычисления суммы грубой силой. Я не уверен, что ваше решение правильно, но это, по крайней мере, правильное мышление для атаки на эту проблему. –
Вот как вы можете рассчитать значение.
Вы вычисляете значение, итеративно, для каждого числа цифр в двоичном представлении верхнего предела. Для каждого числа цифр вычисляется отдельно сумма степеней от 1 до 4 чисел с четным числом единиц и чисел с нечетным числом единиц в их двоичном представлении. Имея эти значения, вы должны иметь возможность вычислять значения для n + 1, где n - число цифр в двоичном представлении.
Вот некоторые замечания о том, как это сделать: если у вас есть сумма k-ых степеней чисел с четным числом единиц, то умножьте это на 2^k, и вы получите сумму этих чисел в два раза , У этих чисел все равно будет четное число. На самом деле каждое число с n числами, имеющими четное число, равно удвоенному числу с n-1 цифрами, имеющим четное число единиц, или x * 2 + 1, где x - число с нечетным числом единиц и имеет n - 1 цифра. Таким образом, сумма k-ых степеней чисел, имеющих четное число единиц в их двоичном представлении и имеющих n цифр, равна Se(n,k) = 2^k * Se(n-1, k) + Sum(a : number with odd number of ones and n-1 digits){(2*a + 1)^k}. Здесь я использую Se для обозначения суммы чисел с четным числом единиц. Теперь интересная часть - второе слагаемое. Его можно рассчитать, используя биномиальную формулу:
(2 * a + 1)^k = 2^k * a * k + комбинация (1, k) * (2 * a)^(k-1) + ... 1 И вот после перегруппировки вас есть: Sum(a : number with odd number of ones and n digits){(2*a + 1)^k} = 2^k*So(n-1,k) + combination(1, k) * 2^(k-1)*So(n-1,k) + combination(2, k) * 2^(k-2)*So(n-1,k) + ...
Теперь, если вы предполагаете, что вы так (сумма чисел с нечетным числом единиц в двоичном представлении), вычисленный для п-1 можно также рассчитать эту сумму ,
Вы должны написать аналогичную формулу для So (п, к):
So (п, к) = 2^к * (So (п-1, к)) + Сумма (а: число с EVEN количество единиц и n-1 цифр) {(2 * a + 1)^k
Помните, что вам нужно вычислить эти значения для k = 1, ... 4, чтобы вы могли использовать их для следующая итерация. Только одно примечание - для So (n, 1) имеем So (n, 1) = So (n-1,1) * 2 + Se (n-1,1) * 2 + 1, аналогично Se (n, 1) = Se (n-1, 1) * 2 + So (n-1, 1).
Используя эти формулы, вы сможете вычислить необходимое вам значение довольно быстро. Вам нужно суммировать Se (1,4) + Se (2,4) + ... Se (64, 4). Алгоритм будет работать для значений, значительно превышающих заданные ограничения. Обратите внимание, что значение, которое вы ищете, не поместится ни в один «обычный» целочисленный тип. Вам нужно будет использовать какую-то реализацию BigInteger.
Надеюсь, это ответит на ваш вопрос.
Каждое второе число имеет четное число бит, поэтому будет около 2^63 = 9223372036854775808 таких чисел. Если вы планируете итерации через них, динамическое программирование вам не поможет. Я думаю, вам нужно будет найти некоторую разделительную математическую связь между числами и упростить проблему, прежде чем начинать писать «для» -loops. – aioobe