主題
題目連結：
題目大意：
定義「快樂數字」為：
一：數字 0 不得出現於位數中。
二：數字 1 ～ 9 皆須出現於位數中。
三：每個相鄰的位數之差不超過 2 。
第一列輸入給定一正整數 N （1 ≦ N ≦ 10 ^ 4），代表接下來有 N 筆測試資料，每筆佔一列。每列給定兩正整數 P 、 Q （1 ≦ P ≦ 10 ^ 3 ， 1 ≦ Q ≦ 9），代表要找 P 位數並以 Q 結尾（也就是個位數為 Q）的快樂數字。
對於每對 P 、 Q 之值，試問這樣的數字有多少個？因為答案可能很大，所以將答案除以 10 ^ 9 + 7 的餘數再輸出即可。
範例輸入：
範例輸入 1：
3
9 1
9 2
9 3
範例輸入 2：
2
12 5
14 7
範例輸出：
範例輸出 1：
31
15
10
範例輸出 2：
27020
2273621
解題思維：
可以看到快樂數字的定義與這題類似（至少規則三是這樣，然後可以直接不用考慮數字 0）。作法也是類似的。但是因為多了一個規則二，也就是 1 ～ 9 都要出現在數字裡，這個稍微麻煩一點。
而我們可以將 1 ~ 9 編碼成一個有 9 位元長的二進位數字，每個位元代表的是一種數字的有無。例如，000001011 代表著有 1 、 2 、 4 這三種數字。編碼方式是由右至左（由左至右當然也行）。
至此，這個編碼就可以作為動態規劃裡的一種新維度，代表著新的狀態。因此加上原先的作法（沒有規則二）時的兩種狀態，現在的動態規劃便成了三維的——其中一維表示數字長度、另一維表示結尾數字，剩下一維表示擁有的數字之種類。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
