把 n 表示成二進位，考慮長度為 4 的情況

n = 1xxy

reverse(n) = yxx1

寫成直式相加來看

  1xxy
+yxx1
----------
?????

把直式相加分成三部分來看

左: 1 + y

中: xx + xx

右: y + 1

計算幾種情形的個數:

1. 中間部分相加後長度不變的組合, 以下簡稱 "不進位的組合" ... (A = 3)

ex:
00+00
01+10
10+01
組合數有3個

2. 中間部分相加後長度增加的組合, 以下簡稱 "進位的組合" ... (B = 1)

ex:
11+11

組合數有1個

3. 不進位的組合 的 1 的個數 ... (C = 4)

00+00=00
01+10=11
10+01=11

1的個數有4個

4. 進位的組合 的 1 的個數 ... (D = 1)

ex:
11+11=110

1的個數有2個

5. 中間部分相加後從右邊算起連續 m 個 1 的組合數 ... (E[m])

ex:

連續 0 個 1 有 2 個: ... (E[0] = 2)

00+00=00
11+11=110

連續 1 個 1 有 0 個 ... (E[1] = 0)

連續 2 個 1 有 2 個: ... (E[2] = 2)

01+10=11
10+01=11

則 f(n + reverse(n)) 可以拆成幾個部分加相

若 y = 0

f(n + reverse(n)) = C + D + A * 2 + B

A * 2 // A種組合左右兩部分的1都有加

B // B種組合只有右邊部分的1有加，左邊部分的1因為中間部分進位而扺消

若 y = 1

f(n + reverse(n)) = C + D + A + B + E[0] - E[2]

A + B // 因左邊部分進位了，所以中間部分不論進位與否都不影響 1 的個數

E[0] // 右邊部分進位，中間部分加完後尾數是 0 的情況

E[2] // 右邊部分進位，中間部分加完後尾數是 1 的情況

最後遞迴計算就可以得到答案

大致上的演算法雛型就這樣

有些小細節沒有詳細說明，留給大家自己想

更正原文打錯的地方:

4. 進位的組合 的 1 的個數 ... (D = 2)

順便補充一下，也可以反向思考以非遞迴方式來解此DP問題

先計算長度為 1 跟 2 的情況，做為初始值，再往兩側增加長度

ex: 計算 n 二進位長度為 7 的所有情況 sum(f(n + reverse(n)), n = 1000000 .. 1111111)

step1. 因為 n 為奇數從長度為1的情況作為初始值

b = 0 或 1

  b
+b

step 2. 左右兩側各增加1長度

a, c = 0或1

  abc
+cba

step 3. 將 step 2 的結果當作新的中間部分b，重覆 step 2，直到長度為與 n 二進位長度相同時，最後一步就只計算 a=1的情況，也就是:

c = 0或1

  1bc
+cb1

 

把 n 表示成二進位，考慮長度為 4 的情況

n = 1xxy

reverse(n) = yxx1

寫成直式相加來看

  1xxy
+yxx1
----------
?????

把直式相加分成三部分來看

左: 1 + y

中: xx + xx

右: y + 1

 

計算幾種情形的個數:

1. 中間部分相加後長度不變的組合, 以下簡稱 "不進位的組合" ... (A = 3)

ex:
00+00
01+10
10+01
組合數有3個

 

2. 中間部分相加後長度增加的組合, 以下簡稱 "進位的組合" ... (B = 1)

ex:
11+11

組合數有1個

 

3. 不進位的組合 的 1 的個數 ... (C = 4)

00+00=00
01+10=11
10+01=11

1的個數有4個

 

4. 進位的組合 的 1 的個數 ... (D = 1)

ex:
11+11=110

1的個數有2個

 

5. 中間部分相加後從右邊算起連續 m 個 1 的組合數 ... (E[m])

ex:

連續 0 個 1 有 2 個: ... (E[0] = 2)

00+00=00
11+11=110

連續 1 個 1 有 0 個 ... (E[1] = 0)

連續 2 個 1 有 2 個: ... (E[2] = 2)

01+10=11
10+01=11

 

則 f(n + reverse(n)) 可以拆成幾個部分加相

若 y = 0

f(n + reverse(n)) = C + D + A * 2 + B

A * 2 // A種組合左右兩部分的1都有加

B // B種組合只有右邊部分的1有加，左邊部分的1因為中間部分進位而扺消

 

若 y = 1

f(n + reverse(n)) = C + D + A + B + E[0] - E[2]

A + B // 因左邊部分進位了，所以中間部分不論進位與否都不影響 1 的個數

E[0] // 右邊部分進位，中間部分加完後尾數是 0 的情況

E[2] // 右邊部分進位，中間部分加完後尾數是 1 的情況

 

最後遞迴計算就可以得到答案

大致上的演算法雛型就這樣

有些小細節沒有詳細說明，留給大家自己想

wpfov-0wig0cfgpfomvk[wmepoksokdaopvml;xxxc;

ak09cv-askbogviva-vavkcmosdk;g

gwrpoajvxovps'bnospojojopjsojcopjbae

heabjop'jarobkeabaBe

qhohwj[httttttttttttttttohaz;',fdh

sp[agmoaegdpgopzvdkf0evr

srcdog[ps,gew0fsdp[avt

acpirm,-t09vectaigrvth

v[avmi0[yi[avl,p[,l[ubbwrgtv

aryya[pmijy-0iahat

jhby-tv9svu

ausrb-yuthi065-vmig0[vgvw

vai[v0cith-r60ifgvha

haha

ohyeah