有一个任务来计算总和，被加数是带有 even number of ones in bin 的数字。以及每个数字的 4 次方。问题是最后一个被加数是 264，所以通常的计算需要很长时间。
我认为动态编程在这里可以有所帮助，但我不知道如何在这里使用它。
这是一个例子:
请问谁能帮我解决这个问题吗？
最佳答案
有一个formula to calculate the sum of the powers of 4 of all integers from 1 to n:
sum(k4) 对于 1<=k<=n = (6*n5 + 15*n 4 + 10*n3 - n)/30
在你的问题中，你只需要对 k 的 4 次方求和，这些 k 的二进制表示中有偶数个。并且这个公式不排除k的个数为奇数的情况。
但是，我的直觉告诉我，奇数个 k 的 4 个幂的总和应该与偶数个 k 的 4 个幂的总和大致相同。
事实证明，如果您计算一系列 k 的这两个总和，这些总和偶尔会完全相同，每 32 k 一次:
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*n5 + 15*n4 + 10*n3 - n)/30)/2
其中 n=264-1。
关于algorithm - 计算具有大量被加数的和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10294007/