USACO Section 3.2 Stringsobits

題目：

給一個二進位數字的長度 N(<= 31)，

求出符合 1 的個數在 L(<= 31)以下的第 I 個二進位數字。


解法：

這題想了滿久的，實在是自己的功力不足啊‧‧‧

我的解法跟官方解不太一樣，可以參考看看，


官方的作法：

首先定義一個狀態，

size[i][j]，表示在長度為 i 時，1 的個數不大於 j 的集合大小，

又集合可以分成，首項是零 或 首項是一，

於是可以得到轉移方程： size[i][j] = size[i-1][j] + size[i-1][j-1]

其中 size[i-1][j] 代表首項由零開始， size[i-1][j-1] 代表首項由一開始，

對於 I，假如 size[N-1][J] > I，則首項必為零，反之首項必為一，

故利用此性質可以做遞迴，求出新的 I，順便印出解答，

如此計算到最後，即為正確答案。


我的作法：

首先可以觀察到一個性質，當數字越大時，

在此數字以下符合 題目性質的數的個數 ，也會是遞增的(非嚴格遞增)，

因此我們可以二分搜找出最接近左界的答案，即為解答，

現在問題就轉換成：

給定一個數字，求出在此數以下所有符合性質的數有幾個。

由於數字大小的特性，只要有效位數大(沒有前導0)則數字就比較大 (ex: 1000 > 111)

此時組合就可以用上場了，舉個例子說明：

假設給定的數字為 1011001 且 L = 3，

迴圈由左到右，當掃到第一個 1 時，右邊的長度還剩下 6，

此時 count += C(6, 3) + C(6, 2) + C(6, 1) + C(6, 0)，

代表著六個位子裡面分別要挑選 3、2、1、0 個給 1 填入的所有組合，

於是就算完了符合性質且不使用第一個 1 的所有情況，

由於上面的特性，可以知道這些數字都不會大於給定的數字，

接下來掃到第二個 1，同理右邊的長度剩下 4，

此時 count += C(4, 2) + C(4, 1) + C(4, 0)，

取的數減一的原因是已經挑了第一個 1，

如此一來就計算完使用第一個 1 但不使用第二個 1 的所有情況，

且這些數依然不會超過給定的數字，

用此方法一直計算到最後，即可求出解答。

這個方法的複雜度不高，因此跑起來相當快。


   Test 1: TEST OK [0.000 secs, 3060 KB]
   Test 2: TEST OK [0.000 secs, 3060 KB]
   Test 3: TEST OK [0.000 secs, 3060 KB]
   Test 4: TEST OK [0.000 secs, 3060 KB]
   Test 5: TEST OK [0.000 secs, 3060 KB]
   Test 6: TEST OK [0.000 secs, 3060 KB]
   Test 7: TEST OK [0.000 secs, 3060 KB]
   Test 8: TEST OK [0.000 secs, 3060 KB]
   Test 9: TEST OK [0.000 secs, 3060 KB]
   Test 10: TEST OK [0.000 secs, 3060 KB]
   Test 11: TEST OK [0.000 secs, 3060 KB]
   Test 12: TEST OK [0.000 secs, 3060 KB]
   Test 13: TEST OK [0.000 secs, 3060 KB]

---

關於組合的部分可以先用預處理的方式計算出來，

方法是利用組合恆等式： C(n, m) = C(n-1, m) + C(n-1, m-1)。