c490. Rabi-Ribi boss 出招問題 - 高中生程式解題系統

內容

你知道四千很喜歡玩Rabi-Ribi。這是個愛冒險的主角Erina，儘管被人們所憎恨，仍然深愛著這個世界的熱血遊戲。

這款遊戲最具特色也最有趣的地方便是boss戰裡的各種彈幕攻擊了。一隻boss擁有 $M$ 種彈幕，在血量降為 $0$ 前不斷選出一種彈幕攻擊Erina。四千雖然知道每種彈幕的躲法，常常卻因為無法及時判斷這是哪種彈幕而讓Erina受傷。有天四千發現，一隻boss的出招順序只跟她的前 $K$ 次攻擊中選擇的彈幕有關。將boss的彈幕編號為 $0, 1, \dots, M - 1$ ，並假設她在第 $i (1 \leq i \leq K)$ 次攻擊選擇了彈幕 $a_{i}$ ，則第 $N$ 次的攻擊招式由下方的C函式給出：

long long ChooseAttack(long long N){
    if(N <= K){
        return a[N];
    }else{
        long long sum = 0;
        for(long long i=1; i<=K; i++){
            sum = sum + c[i]*ChooseAttack(N-i);
        }
        return sum % M;
    }
}

其中 ${c_{i}}_{i = 1}^{K}$ 是個全域long long陣列。不幸的是，四千發現他的C compiler壞了，因為不管等了多久，他的C程式都沒辦法算出ChooseAttack(100000)的值。現在他給你 $M, K, N, {a_{i}}_{i = 1}^{K}, {c_{i}}_{i = 1}^{K}$ ，請你用ZJ的compiler幫他算出ChooseAttack(N)的值。

輸入說明

本題的輸入有 $T$ 筆測資，請讀至檔案尾。

每筆測試資料佔三行。
第一行有三個正整數 $M, K, N$ ，代表意義如上所述。
第二行有 $K$ 個非負整數 $a_{1}, a_{2}, \dots, a_{K}$ ，代表這隻boss前 $K$ 次彈幕攻擊的編號。
第三行有 $K$ 個非負整數 $c_{1}, c_{2}, \dots, c_{K}$ ，代表函式ChooseAttack()中出現的神秘陣列。
每一行的所有整數皆由一個空白隔開，且行末沒有多餘空白。

$1 \leq T \leq 10$
$1 \leq M \leq 10^{7}$
$1 \leq K \leq 20000$ ，且若 $T \geq 2$ ，保證所有的 $K \leq 100$
$1 \leq N \leq 10^{9}$
$0 \leq a_{i} \leq M - 1$
$0 \leq c_{i} \leq M - 1$

輸出說明

對於每筆測試資料，輸出一個介於 $0$ 與 $M - 1$ 之間的整數 $A$ ，代表這隻boss在第 $N$ 次攻擊選擇的彈幕編號，亦即ChooseAttack(N)的值，佔一行。

範例輸入 #1

範例輸出 #1

3
4

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (10%): 5.0s , <1M
不公開測資點#1 (10%): 5.0s , <1M
不公開測資點#2 (10%): 5.0s , <1M
不公開測資點#3 (10%): 5.0s , <1M
不公開測資點#4 (10%): 5.0s , <1M
不公開測資點#5 (10%): 5.0s , <1M
不公開測資點#6 (10%): 5.0s , <1M
不公開測資點#7 (10%): 5.0s , <1M
不公開測資點#8 (10%): 5.0s , <1M
不公開測資點#9 (10%): 5.0s , <1M

提示：

第一筆測資中，boss在第 $N$ 次攻擊放的彈幕編號恰為費氏數列第 $N - 1$ 項的個位數，故 $A = 3$ 。
第二筆測資中，不難觀察到boss放彈幕的順序為 $0, 1, 2, 3, 4, 0, 1, 2, 3, 4, \dots$ ，故 $A = 4$ 。
那張圖片中的攻擊雖然看起來很可怕，其實只要站著不動就不會被打到。
如果你對那張圖片中的boss戰有興趣，可以看看這個。

標籤:

數學

出處:

經典問題 [管理者： xavier13540 (柊四千) ]

編號	身分	題目	主題	人氣	發表日期
13272	xavier13540 (柊四千)	c490	作者提供的解法	1096	2018-01-22 23:42