刷題比賽

題目描述

給你四個數組A,B,C,D. 給出每個數組的初始值A[1] = 1, B[1] = 1, C[1] = 1, D[1] =1 , A[2] = 3, B[2] = 3, C[2] = 3, D[2] = 3;
有以下的遞推公式:
(1) a[k+2]=p* a[k+1]+qa[k]+b[k+1]+c[k+1]+r k^2+t * k+1+d[k];
(2)b[k+2]=u* b[k+1]+vb[k]+a[k+1]+c[k+1]+w^k+d[k];
(3)c[k+2]=x c[k+1]+yc[k]+a[k+1]+b[k+1]+z ^ k+k+2+d[k];
(4)d[k+2]=e d[k+1]+f*d[k];
（以上的字母p,q,r,t,u,v,w,x,y,z,e,f都是給定的常數，并保證是正整數)
由于結果很大,輸出a[k] mod k,b[n] mod k,c[n] mod k, d[n] mod k;(4<=n<=10^12)

輸入格式：

第一行兩個正整數N,K。(4<=N<=10^12，2<=K<=10^16)
第二行四個正整數p,q,r,t。
第三行三個正整數u,v,w。
第四行三個正整數x,y,z。
第五行兩個正整數e,f.
(保證p,q,r,t,u,v,w,x,y,z,e,f都是不超過100的正整數)

輸出格式：

共三行，每行一個整數。依次是這四個數組 mod K的值。

輸入樣例#1：

輸出樣例#1：

說明

矩陣乘法。

注意，中間相乘過程可能會比64位長整型的數據范圍還要大。

solution

20%的做法:

按照題目給出的式子直接模擬計算即可

60%的做法:

運用矩陣快速冪,我們需要構造出一個合格的答案矩陣和一個合格的轉移矩陣.
經過一番推演后可以得到一個13 * 13的轉移矩陣
0 1 0 0 0 0 0 0 0 0 0 0 0 ak
q p 0 1 0 1 1 0 r t 1 0 0 ak+1
0 0 0 1 0 0 0 0 0 0 0 0 0 bk
0 1 v u 0 1 1 0 0 0 0 1 0 bk+1
0 0 0 0 0 1 0 0 0 0 0 0 0 ck
0 1 0 1 y x 1 0 0 1 2 0 1 ck+1
0 0 0 0 0 0 0 1 0 0 0 0 0 dk
0 0 0 0 0 0 f e 0 0 0 0 0 dk+1
0 0 0 0 0 0 0 0 1 2 1 0 0 k^2
0 0 0 0 0 0 0 0 0 1 1 0 0 k(初始值為1)
0 0 0 0 0 0 0 0 0 0 1 0 0 1(恒為一)
0 0 0 0 0 0 0 0 0 0 0 w 0 w^k (初始值為w)
0 0 0 0 0 0 0 0 0 0 0 0 z z^k (初始值為z)
對這兩個矩陣進行n-2次快速冪即可(當然,右邊的矩陣要填上一堆0,使得這個矩陣也成為13*13的規模). (只能得60分是因為其他的點乘法運算會爆longlong)
對于65%的做法,我們把60%程序中的longlong 改為unsigned long long 即可得65分

100%的做法:

100%的做法是在60%的做法上面進行改進的,因為中途運算會爆longlong,所以我們在矩陣乘法的時候不能使用單純的乘法,應該用快速冪加法來代替乘法.
這樣就可以得100%分了.