自從william當上了進階助教後，發現其他幹部都好電，只有他不會DP，而且奇怪的是，每隔一段時間，都會有匿名的人傳給william題目，上一次的題目他花了一整節自習課才算出來。今天他又收到一封訊息了，請你幫william解決這個難題吧!
當$N$可被2 or 3 or 5 整除時 輸出0
另$K$為$N$的倍數，且每一位都是1。(ex:111111)
對於最小的$K$，隨機的讓$K$的每一位數變成1或0
如果$K$仍可被$N$整除，定義這個數為好數。
總共會出現幾種好數 $mod 10^9 + 7$
第一行有一數$T$，代表有$T$筆測資
接下來有$T$行，每一行輸入一數$N$
對於$K$的每一位數，隨機的讓1變成0，總共會出現幾種好數。
3 7 13 19
10 10 13798
前50%測資 $T \leq 100 \quad N \leq 2*10^3$
100% 測資$T \leq 500 \quad N \leq 10^4$
當$N$為7時 $K$ = $111111$
符合題序的數為:
{0,1001 ,10010 ,10101 ,11011 ,100100 ,101010 ,101101 ,110110 ,111111}
共十種
$N的值是隨機的$
$使用複雜度O(N^2)即可通過$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||