1、 矩陣及其應(yīng)用 雍高鵬矩陣乘法及其優(yōu)化對于整形數(shù)字b=ak%m，當(dāng)k很大的時(shí)候（1e9），可以用二分的思想快速求出b的值?？焖賰缒敲?，類似的，對于矩陣s，sk%mod也可以快速求出。復(fù)雜度分析，在算法競賽中，矩陣的規(guī)模不會太大，乘法的O(N3)當(dāng)做常數(shù)處理。Sk可以用二分求解，如果是S1+S2+.+Sk呢？答案就是，二分，再二分?？焖賰缟厦鎚at_plu()是矩陣相加的函數(shù)，對應(yīng)位置相加。以k=16為例：s1+s16=(s1+s8)+s8(s1+s8)s1+s8=(s1+s4)+s4(s1+s4)規(guī)模依次折半。給定n個(gè)點(diǎn)，對所有點(diǎn)同時(shí)進(jìn)行m個(gè)操作（操作包括平移、縮放、翻轉(zhuǎn)和旋轉(zhuǎn)），試構(gòu)造O(m

2、+n)的算法輸出m個(gè)操作后各點(diǎn)的位置。其中翻轉(zhuǎn)是以坐標(biāo)軸為對稱軸進(jìn)行翻轉(zhuǎn)（兩種情況），旋轉(zhuǎn)則以原點(diǎn)為中心。關(guān)于構(gòu)造一張N個(gè)點(diǎn)的無向無權(quán)圖。如果點(diǎn)a和點(diǎn)b之間有邊，那么鄰接矩陣Gab = Gb a = 1，否則等于0。那么，考慮鄰接矩陣自乘，即G2，會有什么意義。若G2ab！=0，就說明存在點(diǎn)i，使得a i 間有邊并且i b 間也有邊。G2ab的值，即為從點(diǎn)a到點(diǎn)b經(jīng)過1個(gè)中間點(diǎn)的路徑條數(shù)。對于G3,即Ga iGi jGj b = 1當(dāng)且僅當(dāng)Gai = Gi j = Gj b =1，也就是說aijb組成一條路經(jīng)。那么G3a b的值就是從點(diǎn)a到點(diǎn)b經(jīng)過2個(gè)中間點(diǎn)的路徑條數(shù)。因此，運(yùn)用數(shù)學(xué)歸納法不難

3、證明， Gka b就等于a到b經(jīng)過k-1個(gè)中間點(diǎn)也就是長度為k的路徑條數(shù)。圖的鄰接矩陣的應(yīng)用一些推廣及處理：1、前面的結(jié)論同樣適用于有向圖。2、對于有重邊的圖，只需要把Ga b改為表示點(diǎn)a, b之間重邊的數(shù)目。3、對于有向圖的自環(huán)，直接加邊即可。4、對于無向圖的自環(huán)，通常是把Gaa加上2，這樣在計(jì)算Gk的時(shí)候這條邊就被算成2條不同的邊，如果只加上1，又會不滿足矩陣?yán)锼性睾偷扔谶厰?shù)兩倍的性質(zhì)(入度和出度)。5、忽略前面所說的，具體問題具體分析。圖的鄰接矩陣的應(yīng)用有K種珍珠，每種N顆，求這些珍珠組成的長度在1N之間包含K種珍珠的項(xiàng)鏈有多少種（答案模1234567891）。其中，1=K=30,1

4、=N=1000,000,000狀態(tài)轉(zhuǎn)移方程：dpij = j*dpi-1j+(k-j+1)*dpi-1j-1.其中 dpij表示包含j種珍珠且長度為i的項(xiàng)鏈的種數(shù)。ans= dp1k+dpnk直接開dp數(shù)組會MLE，用滾動數(shù)組O(nk)遞推會TLE.注意到，dpi的狀態(tài)只與dpi-1相關(guān)，那么從狀態(tài)dpi-1轉(zhuǎn)移到狀態(tài)dpi，相當(dāng)于一個(gè)k*k的線性變化。即Fi=A*Fi-1，這里A是轉(zhuǎn)移矩陣，即Fi=Ai-1*F1，所以ans=F1+Fn=A0*F1+An-1*F1=(E+A+A2+An-1)*F1。 (注意這里有矩陣，自己構(gòu)造自己想)優(yōu)化DP使用矩陣優(yōu)化的條件：1、狀態(tài)必須是一維或者兩維，如果狀態(tài)本身有超過兩維要狀態(tài)壓縮。2、每一個(gè)狀態(tài)dpi 必須滿足只和dpi-1 有關(guān)，并且只能是線性關(guān)系3、轉(zhuǎn)移矩陣都相同或者至少是循環(huán)出現(xiàn)才能通過快速冪加速。4、矩陣規(guī)模較小，轉(zhuǎn)移次數(shù)較大的時(shí)候才運(yùn)用，否則很可能增加復(fù)雜度優(yōu)化DPPOJ 3233 POJ 3070 POJ 3735HDU 3306HDU 1757HUD 2294ZOJ 2974