音無結弦之時，悅動天使之心。立於浮華之世，奏響天籟之音。
(圖片來源：每日頭條)
這是一首詩，詩中描述音樂是永不截止的，而且在物質享受豐富的現代演奏，就一定要奏響世上最美的聲音，悅動天使的心。
據說聽到這句詩的人都會發狂地突然去學鋼琴，企圖奏響天籟之音。
William 看到這首詩之後，也不免俗地著了魔，並且燃起對音樂的熱忱。
他知道世界上有一些歌的歌譜已經失傳了，為此他非常的氣憤。
他想要把這些歌的歌譜給重現出來，但他只知道一些音符，還只知道它佔幾拍。
因此他覺得：如果我可以把旋律重建出來就很好了，但是把音高重現......等我變更強再說
這是一件浩大的工程，因此 William 邀請你和他合作。
他把音譜的節拍寫在紙上，其中：
$M$ 代表二分音符 (Minim)
$C$ 代表四分音符 (Crotchet)
$Q$ 代表八分音符 (Quaver)
$S$ 代表十六分音符 (Semiquaver)
$?$ 代表不知道，它可能是二分音符、四分音符、八分音符或是十六分音符。
已知在一個樂譜 $\Large _m^n$ 拍的情況下，代表「每個小節有 $n$ 拍，$m$ 分音符為一拍」，
且每個音譜必定有整數個小節，每個小節必定包含整數個音符。
由於 William 做這個重建工作還在嘗試期，因此他必須把所有可能的節拍都寫出來並一一彈奏，這樣才能知道哪個譜最像是失傳的音譜。
身為 William 的朋友，也身為一位熟悉電腦的人才，你看他手推樂譜非常可憐，所以你決定使用你的電腦之力來讓他的工作速度加快。
William 聽到你的提議後，當然是非常樂意把工作分給你，但又怕自己的好友太累，因此他說：
「你告訴我每個譜有多少種重建方法就好，這樣我也可以知道這首歌值不值得重建......畢竟越少組合數的歌重建起來越快嘛！」
而你也不想讓好朋友傷心，所以只要音譜重建方法達到 $1000000007$ 種以上，你就會把目前找到的重建方法數扣掉 $1000000007$ 再繼續運算，
一方面讓自己的電腦運算比較方便，一方面也可以使答案少於 $1000000007$，讓 William 看到這重建方法數後可以對這首歌燃起鬥志 (殊不知你陰了他)
現在，對於 William 給你的每首歌，告訴他「你算出來的」重建方法數有多少吧！
第一行依序有兩數 $n,\;m$，代表音譜是 $\Large _m^n$ 拍，
第二行則是一個字串 $w$，代表 William 給你的音譜。
$w[i]\in \{M, C, Q, S, ?\}$
輸出一個整數，代表題目要求之答案。
4 4 ?M??
4
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (10%): 1.0s , <1M
公開 測資點#13 (10%): 1.0s , <1M
公開 測資點#14 (10%): 1.0s , <1M
公開 測資點#15 (10%): 1.0s , <1M
$10\%$ 測資，$w[i]\in \{M, C, Q, S\}$, $\lvert w\rvert\leq 10$
$10\%$ 測資，$w[i] = ?$ 之數量 $<10$ , $\lvert w\rvert\leq 10$
$20\%$ 測資，$w[i] = ?$, $\lvert w\rvert\leq 1000$
$20\%$ 測資，$\lvert w\rvert\leq 10^4$
$40\%$ 測資，無特殊限制。
$100\%$ 測資，$2\leq n\leq 9$, $m\in \{2, 4, 8\}$, $3\leq\lvert w\rvert\leq 10^6$
範例測資中，$"CMQQ", "QMCQ", "QMQC", "MMMM"$ 皆符合音譜規定，故答案為 $4$ 種。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||