合計を数えるタスクがあります。これは、bin に偶数の 1 があり、各数値が 4 乗された数値です。問題は、最後の被加数が 2 64であるため、通常の計算では時間がかかることです。ここでは動的計画法が役立つと思いますが、ここでの使用方法がわかりません。
次に例を示します。
お願いします、誰かこの問題を手伝ってくれませんか?
質問する
699 次
2 に答える
1
値を計算する方法は次のとおりです。
上限のバイナリ表現の桁数ごとに値を繰り返し計算します。桁数ごとに、バイナリ表現で偶数の 1 を持つ数と奇数の 1 を持つ数の次数 1 から 4 の合計を個別に計算します。これらの値があれば、n+1 の値を計算できるはずです。ここで、n はバイナリ表現の桁数です。
これを行う方法に関するいくつかの観察事項を次に示します。 k 次数の合計が偶数の 1 である場合、これに 2^k を掛けると、これらの数の合計が 2 倍になります。これらの数字には偶数の 1 があります。実際、偶数の 1 を持つ n 桁の各数値は、偶数の 1 を持つ n-1 桁の 2 倍の数値であるか、x * 2 + 1 であり、x は奇数の 1 を持つ数値であり、n - 1桁。したがって、バイナリ表現で偶数の 1 を持ち、n 桁の数の k 次数の合計は です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 を使用して、偶数の 1 を含む数の合計を示します。ここで興味深い部分は 2 番目の加数です。二項式を使用して計算できます。
(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) + ...
ここで、n-1 に対して計算された So (バイナリ表現で奇数の 1 を含む数の合計) があると仮定すると、この合計も計算できます。
So(n,k) についても同様の式を書く必要があります。
So(n,k) = 2^k*(So(n-1, k)) + Sum(a : 偶数の 1 と n-1 桁の数){(2*a + 1)^k
次の反復で使用できるように、k = 1、... 4 についてこの値を計算する必要があることに注意してください。1 つのメモのみ - 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 実装を使用する必要があります。
これがあなたの質問に答えることを願っています。
于 2012-04-24T09:12:23.797 に答える
1
1 から n までのすべての整数の 4 乗の合計を計算する式があります。
sum(k 4 ) for 1<=k<=n = (6*n 5 + 15*n 4 + 10*n 3 - n) / 30
あなたの問題では、バイナリ表現に偶数の 1 がある k の 4 の累乗のみを合計する必要があります。そして、この式は k の 1 の数が奇数であることを除外しません。
ただし、私の直感では、奇数の 1 を持つ k の 4 乗の合計は、偶数の 1 を持つ k の 4 乗の合計とほぼ同じになるはずです。
k の範囲に対してこれら 2 つの合計を計算すると、これらの合計は 32 k ごとに 1 回、まったく同じになることがわかります。
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*n 5 + 15*n 4 + 10*n 3 - n) / 30) / 2
ここで、n=2 64 -1。
于 2012-04-24T09:59:46.753 に答える