c491. Hollow Knight boss 出招問題 - 高中生程式解題系統

內容

你知道四千很喜歡玩Hollow Knight。遊戲中的小騎士，在深入地底探索這充滿bug的世界的同時，也探索自身存在的意義。

這款遊戲最具特色也最有趣的地方便是boss戰裡的各種攻擊招式了。一隻boss擁有 $M$ 種招式，在血量降為 $0$ 前不斷選出一種招式攻擊小騎士。四千雖然知道每種招式的躲法，常常卻因為無法及時判斷這是哪種招式而讓小騎士受傷。有天四千發現，一隻boss的出招順序是一個 $Q$ 循環。將boss的招式編號為 $0, 1, \dots, M - 1$ ，則第 $N (1 \leq N \leq Q)$ 次的攻擊招式由下方的C函式給出：

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

其中 $K$ 是個全域long long變數，而 ${a_{i}}_{i = 1}^{Q}$ 和 ${c_{i}}_{i = 0}^{K}$ 都是全域long long陣列。不幸的是，四千發現他的C compiler又壞了，因為當 $K = 60000$ 時，光是計算ChooseAttack(1)就花了他幾十秒，更別提算完ChooseAttack(2), ChooseAttack(3), ..., ChooseAttack(Q)了。現在他給你 $M, Q, K, {a_{i}}_{i = 1}^{Q}, {c_{i}}_{i = 0}^{K}$ ，請你用ZJ的compiler幫他算出ChooseAttack(1), ChooseAttack(2), ..., ChooseAttack(Q)的值。

輸入說明

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

每筆測試資料佔三行。
第一行有三個正整數 $M, Q, K$ 。
第二行有 $Q$ 個非負整數 $a_{1}, a_{2}, \dots, a_{Q}$ 。
第三行有 $K + 1$ 個非負整數 $c_{0}, c_{1}, \dots, c_{K}$ 。
每一行的所有整數皆由一個空白隔開，且行末沒有多餘空白。

$1 \leq T \leq 10$
$1 \leq M \leq 10^{8}$
$1 \leq Q \leq 60000$ ，且若 $T \geq 2$ ，保證所有的 $Q \leq 100$
$1 \leq K \leq 60000$ ，且若 $T \geq 2$ ，保證所有的 $K \leq 100$
$0 \leq a_{i} \leq M - 1$
$0 \leq c_{i} \leq M - 1$

輸出說明

對於每筆測試資料，輸出一行，包含 $Q$ 個介於 $0$ 與 $M - 1$ 之間的整數 $A_{1}, A_{2}, \dots, A_{Q}$ ，其中 $A_{N}$ 代表這隻boss在第 $N$ 次攻擊選擇的招式，亦即ChooseAttack(N)的值。

每一行的所有整數應皆由一個空白隔開，且行末不應有多餘空白。

範例輸入 #1

範例輸出 #1

1 2 5 0
0 4 4 4

測資資訊：

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

提示：

如果你對圖片上的boss戰有興趣，你可以參考這個。
蛤？你問我為什麼 $M$ 居然會比 $Q$ 大？我也不知道，可能是因為即便是同一場boss戰，每次生出來的 ${a_{i}}_{i = 1}^{Q}$ 和 ${c_{i}}_{i = 0}^{K}$ 都不同吧。

標籤:

數學

出處:

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

編號	身分	題目	主題	人氣	發表日期
13281	xavier13540 (柊四千)	c491	作者提供的解法	1101	2018-01-24 22:27