f171: m5a2-快樂數字(HappyNumber)
Tags : 動態規劃 狀態壓縮
Accepted rate : 8人/10人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-09 15:37

Content

TOI練習賽 2020m5a2-快樂數字(HappyNumber)   原題連結 

問題敘述
小巴跟小華發明了一種新的遊戲,名字為「快樂數字」。這個遊戲的玩法
如下,兩人遵照規則輪流說出一個符合條件的快樂數字,先說不出數字或數字
重複的人就輸了,其規則如下:
(1) 快樂數字不包含 0。
(2) 快樂數字須包含 1~9 的每個數字。
(3) 在快樂數字中,相鄰的位數數字之差至多為 2。
給定快樂數字的位數以及其個位數字,請你寫一個程式計算符合此條件的
快樂數字共有幾個,由於數字可能過大,因此請輸出個數除以 109+7 的餘數。

評分說明
此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資
料才能獲得該組分數。各組詳細限制如下。
第一組 (10 分) : 1<=P<=10
第二組 (30 分) : 1<=P<=10^2
第三組 (60 分) : 1<=P<=10^3

 

Input

輸入第一行有一個正整數 N(1<=N<=10^4),代表詢問數;
緊接著共有 N 行,每行有兩個正整數 P(1<=P<=10^3)、
Q(1<=Q<=9),代表詢問以 Q 結尾的 P 位數快樂數字共有幾個。

Output

對於每個詢問,請輸出快樂數字個數除以 10^9+7 的餘數。

Sample Input #1
3
9 1
9 2
9 3
Sample Output #1
31
15
10
Sample Input #2
2
12 5
14 7
Sample Output #2
27020
2273621
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :
Tags:
動態規劃 狀態壓縮
出處:
TOI練習賽2020年5月潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」