c490: Rabi-Ribi boss 出招問題
標籤 : 數學
通過比率 : 50% (1 人 / 2 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-01-24 11:44

內容

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

Lilli & Pixie

這款遊戲最具特色也最有趣的地方便是boss戰裡的各種彈幕攻擊了。一隻boss擁有$M$種彈幕,在血量降為$0$前不斷選出一種彈幕攻擊Erina。四千雖然知道每種彈幕的躲法,常常卻因為無法及時判斷這是哪種彈幕而讓Erina受傷。有天四千發現,一隻boss的出招順序只跟她的前$K$次攻擊中選擇的彈幕有關。將boss的彈幕編號為$0, 1, \ldots, 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, \ldots, a_K$,代表這隻boss前$K$次彈幕攻擊的編號。
第三行有$K$個非負整數$c_1, c_2, \ldots, 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)的值,佔一行。

範例輸入
10 2 8
0 1
1 1
5 5 100000
0 1 2 3 4
0 0 0 0 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
提示 :
  1. 第一筆測資中,boss在第$N$次攻擊放的彈幕編號恰為費氏數列第$N-1$項的個位數,故$A=3$。
    第二筆測資中,不難觀察到boss放彈幕的順序為$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, \ldots$,故$A=4$。
  2. 那張圖片中的攻擊雖然看起來很可怕,其實只要站著不動就不會被打到。
  3. 如果你對那張圖片中的boss戰有興趣,可以看看這個
標籤:
數學
出處:
經典問題 [編輯:
xavier13540 (柊 四千)
]


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