問題描述 Description
現定義序列它的第i項為： Fi=Si?1?Fi?1+Si?2?Fi?2 定義F0=0以及F1=1 其中，S是一個無限長的，幾乎循環的一個數字序列，它的循環節長度為N，也就是說，通常會有Si=SimodN。但是S中也存在少數元素并不符合這個循環節，也就是說，會有若干個元素，Si≠SimodN。 現在給出序列S的循環節，以及S中不符合循環的位置以及值，求FkmodP。
輸入 Input
輸入文件的第一行有兩個整數K和P。 第二行是一個整數N。 第三行包含N個正整數，表示循環節中所有的數字。 接下來一行是一個整數M。接下來的M行，每行包含兩個整數x和y，表示在序列S中不符合循環節的位置以及相應位置上的值，即Sx=y。
輸出 Output
輸出文件包含一個整數，即相應輸入文件的答案。
樣例輸入 Sample Input
42 1248493 5 5 2 4 1 6 5 9 3 8 4 21 21 10 18 24 10
樣例輸出 Sample Output
232959
限制 Limits
對于30%的數據：0≤k≤10000,1≤n≤1000,1≤M≤20； 對于70%的數據：0≤k≤1018,1≤n≤1000,1≤M≤20； 對于100%的數據：0≤k≤1018,1≤n,m≤5×104,1≤p≤109,1≤Si≤109,n≤x≤1018,1≤y≤109 。 Time Limit : 2s & Memory Limit : 128MB
一看k這么大快速冪逃不掉了…… 一看遞推關系矩陣逃不掉了…… 所以矩陣快速冪逃不掉了。 MDZZ怎么搞矩陣？ 這回在化學課上推公式…… f0=0f1=1f2=s1f1=s1f3=s2f2+s1f1=s1s2+s1f4=s3f3+s2f2=s1s2s3+s1s2+s1s3...... 看出什么來了嗎？ 反正我看了一天 可以看出這個f只與s有關…… 假如能搞出一個矩陣的話，可以借鑒分塊思想，將一個循環節看成一個塊，將整個塊內的值求出后，跑矩陣快速冪，之后零散部分暴力。 可是有修改…… 就將修改看成斷點，假如斷點處于同一塊內，暴力即可，如果不在，零散暴力，整塊快速冪。 時間為O(mnlogk) 這樣可以過70%…… 100%優化的是零散部分，因為要不停計算零散部分，這些零散部分還是循環的，所以可以用線段樹優化。 時間為O(mlognlogk) 所以，怎么構造矩陣？ 還是兩個矩陣，一個是處理影響的，一個是統計答案的。 統計答案的矩陣是一個1×2的矩陣： [fa+1fa] 當然也可以寫成2×2的，其余補0即可。 處理影響的矩陣是一個2×2的矩陣： [01sasa+1] 遇到斷點答案矩陣暴力乘矩陣即可，此矩陣為： [01sx?1c] 其中x為需要修改的位置，c為變換成的數。 這還沒完，因為矩陣與x+1位置也有關，還需要乘： [01csx+1] 這樣就可以了 還有一些許多細節需要注意……具體參見代碼。 Code
