2
合計を計算するタスクがあります。even number of ones in binの数値であり、各数値は4の累乗になります。問題は最後の被加数が2 なので通常の計算には長い時間がかかります。 ダイナミックプログラミングはここで助けになると思いますが、ここでどのように使用するのか分かりません。
ここでは例です：、
多数の合計を持つ合計を計算する
してください誰もがこの問題で私を助けることができますか？
A
答えて
1
formula to calculate the sum of the powers of 4 of all integers from 1 to nがあります：
和（K ） = K < = N =（6×n個 + 15 * nの + 10 * N 3について - n）/ 30
問題では、バイナリ表現で偶数の1を持つkの4の累乗だけを集計する必要があります。この数式は、奇数個のkを除外しません。
しかし、奇妙な数を持つkの4のべき乗の和は、kの4の累乗と偶数の累乗の和とほぼ同じである必要があります。
それはあなたが、Kさんの範囲のためにこれらの2点の合計を計算する場合、これらの合計が一回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×n個 + 15 * nの + 10 * N - N）/ 30）/ 2
ここで、n = 2 -1。
+0
これを正しく理解していれば 'n'はビット数を表しますか？したがって、テーブルの各行について、奇数合計は、奇数パリティを持つすべてのnビット数の4乗の合計です。偶数パリティのnビットの数値の偶数の和は？私の理解が正しい場合、表の最初の間違いはn = 2であり、偶数の合計は81（11バイナリ== 10進数、3^4 = 81）でなければなりません。テーブルはまた、nの3つの連続する値の偶数合計が同じである多数の他の場所においても間違っている（例えば、n = 24,25,26）。私が誤解した場合は、明確にしてください。この問題以外に、私は答えが好きです。 –
+0
「n」は、合計で4の累乗に上げる最大数です。問題文では、0から3,5,6,9,10,12,15、...、2^64-1になります。テーブルの中に何が入っているかを見るために、数字の4のべき乗の和を、奇数と偶数の数字の4つの数字の和を手で入力します。私のテーブルは、4の累乗と偶数の累乗を正確に再現します。次の「n」は「奇数」または「偶数」の和に寄与しますが、両方ではないので、「dups」はそこにあります.nは偶数と奇数を同時に持つことができないからです。 –
+0
総数をブルートフォースで計算するのではなく、数式を使って閉形式の解法（一定の時間！私は必ずしもあなたの解決策は正しいとは確信していませんが、これは少なくともこの問題を攻撃する正しい考え方です。 –
1
値を計算する方法は次のとおりです。
上限のバイナリ表現の各桁数に対して反復的に値を計算します。各桁数に対して、偶数の1の数と奇数の1の数の2進数表現の度1から4の合計を別々に計算します。これらの値を持つと、n + 1の値を計算できるはずです.nはバイナリ表現の数字の数です。
これを行うにはいくつかの観察があります：k番目の次数と1の偶数の和をとった場合、これに2^kを掛けると、これらの数の合計が2倍になります。これらの数字はまだ偶数である。実際には、偶数の桁を持つn桁の各数字は、偶数が1であるn-1桁の倍数、または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を使用して、偶数の数字の合計を示します。今興味深い部分は第2の要約です。これは、2項式を使用して計算することができる。
（2 * a + 1）k = 2k * a * k +（1、k）*（2 * a）^（k-1）+ ...あなたが持っている再編後の1だから：あなたはので（そのバイナリ表現における1の奇数番号の数字の合計が）は、n-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、K）：だから
（N、K）= 2^k個の*（SO（N-1、K））+合計（：数と1、...、4）の値を計算する必要がありますので、k = 1、...、4の値を計算する必要があります。次の反復。同様に、Se（n、1）= So（n-1,1）* 2 + Se（n-1,1）* 2 + 1をSo（n、1） ）= Se（n-1,1）* 2 + So（n-1,1）となる。
これらの式を使用すると、必要な値を非常に高速に計算できるはずです。あなたはSe（1,4）+ Se（2,4）+ ... Se（64、4）を合計する必要があります。このアルゴリズムは、与えられた制約よりもかなり高い値に対して機能します。検索している値が「通常の」整数型に収まらないことに注意してください。何らかの種類のBigInteger実装を使用する必要があります。
これはあなたの質問にお答えします。
関連する問題
- 1. 計算合計
- 2. 合計を計算し、多くを数えます
- 3. Django集計合計を計算する
- 4. スカラ：計算合計
- 5. アクティブレコード合計計算
- 6. ノックアウト計算合計
- 7. クライアント側の2つの整数の合計を計算する
- 8. 2つの変数の合計を計算する
- 9. 同じidを持つ行の合計を計算
- 10. 角度4 in * ngFor合計値の合計を計算する
- 11. SQLクエリを計算合計
- 12. 複数のファイルから合計統計を計算する
- 13. いくつかの合計の計算
- 14. 複数のサブセット合計の計算
- 15. postgresql resultsetの合計を計算する
- 16. スカラーリストの合計を計算する
- 17. 配列の合計を計算する
- 18. サブフォームの合計を計算する
- 19. mysqliデータベースの合計を計算する
- 20. jQueryの全行と合計の合計を計算します
- 21. Rails - 計算の合計
- 22. Stataでの合計計算
- 23. Javascriptの計算割合の合計キー
- 24. Access SQLクエリ - 合計計算の割合
- 25. 年合計を計算する
- 26. PHPExcelで合計を計算する
- 27. 合計値を計算する
- 28. 合計金額を計算する
- 29. SQLサーバーで合計を計算する
- 30. C++で合計を計算する
2番目の数字はすべて偶数ビットなので、2^63 = 9223372036854775808となります。それらをすべて反復処理する予定がある場合は、動的プログラミングは役に立ちません。私は数字の間に数学的な関係を見つける必要があり、 "for"ループを書き始める前に問題を単純化しなければならないと思います。 – aioobe