沼澤鱷魚

【題目描述】

潘塔納爾沼澤地號(hào)稱世界上最大的一塊濕地，它地位于巴西中部馬托格羅索州的南部地區(qū)。每當(dāng)雨季來臨，這里碧波蕩漾、生機(jī)盎然，引來不少游客。

為了讓游玩更有情趣，人們?cè)诔靥恋闹醒虢ㄔO(shè)了幾座石墩和石橋，每座石橋連接著兩座石墩，且每?jī)勺罩g至多只有一座石橋。這個(gè)景點(diǎn)造好之后一直沒敢對(duì)外開放，原因是池塘里有不少危險(xiǎn)的食人魚（不是說鱷魚咩~_~）。

豆豆先生酷愛冒險(xiǎn)，他一聽說這個(gè)消息，立馬趕到了池塘，想做第一個(gè)在橋上旅游的人。雖說豆豆愛冒險(xiǎn)，但也不敢拿自己的性命開玩笑，于是他開始了仔細(xì)的實(shí)地勘察，并得到了一些驚人的結(jié)論：食人魚的行進(jìn)路線有周期性，這個(gè)周期只可能是2，3或者4個(gè)單位時(shí)間。每個(gè)單位時(shí)間里，食人魚可以從一個(gè)石墩游到另一個(gè)石墩。每到一個(gè)石墩，如果上面有人它就會(huì)實(shí)施攻擊，否則繼續(xù)它的周期運(yùn)動(dòng)。如果沒有到石墩，它是不會(huì)攻擊人的。

借助先進(jìn)的儀器，豆豆很快就摸清了所有食人魚的運(yùn)動(dòng)規(guī)律，他要開始設(shè)計(jì)自己的行動(dòng)路線了。每個(gè)單位時(shí)間里，他只可以沿著石橋從一個(gè)石墩走到另一個(gè)石墩，而不可以停在某座石墩上不動(dòng)，因?yàn)檎局粍?dòng)還會(huì)有其它危險(xiǎn)。如果豆豆和某條食人魚在同一時(shí)刻到達(dá)了某座石墩，就會(huì)遭到食人魚的襲擊，他當(dāng)然不希望發(fā)生這樣的事情。

現(xiàn)在豆豆已經(jīng)選好了兩座石墩Start和End，他想從Start出發(fā)，經(jīng)過K個(gè)單位時(shí)間后恰好站在石墩End上。假設(shè)石墩可以重復(fù)經(jīng)過（包括Start和End），他想請(qǐng)你幫忙算算，這樣的路線共有多少種（當(dāng)然不能遭到食人魚的攻擊）。

?

【輸入文件】

輸入文件共M + 2 + NFish行。

第一行包含五個(gè)正整數(shù)N，M，Start，End和K，分別表示石墩數(shù)目、石橋數(shù)目、Start石墩和End石墩的編號(hào)和一條路線所需的單位時(shí)間。石墩用0到N–1的整數(shù)編號(hào)。

第2到M + 1行，給出石橋的相關(guān)信息。每行兩個(gè)整數(shù)x和y，0 ≤ x, y ≤N–1，表示這座石橋連接著編號(hào)為x和y的兩座石墩。

第M + 2行是一個(gè)整數(shù)NFish，表示食人魚的數(shù)目。

第M + 3到M + 2 + NFish行，每行給出一條食人魚的相關(guān)信息。每行的第一個(gè)整數(shù)是T，T = 2，3或4，表示食人魚的運(yùn)動(dòng)周期。接下來有T個(gè)數(shù)，表示一個(gè)周期內(nèi)食人魚的行進(jìn)路線。

? ? ? 如果T＝2，接下來有2個(gè)數(shù)P₀和P₁，食人魚從P₀到P₁，從P₁到P₀，……；

? ? ? 如果T＝3，接下來有3個(gè)數(shù)P₀，P₁和P₂，食人魚從P₀到P₁，從P₁到P₂，從P₂到P₀，……；

? ? ? 如果T＝4，接下來有4個(gè)數(shù)P₀，P₁，P₂和P₃，食人魚從P₀到P₁，從P₁到P₂，從P₂到P₃，從P₃到P₀，……。

豆豆出發(fā)的時(shí)候所有食人魚都在自己路線上的P₀位置，請(qǐng)放心，這個(gè)位置不會(huì)是Start石墩。

?

【輸出文件】

輸出路線的種數(shù)，因?yàn)檫@個(gè)數(shù)可能很大，你只要輸出該數(shù)除以10000的余數(shù)就行了。

?

【約定】

???????1 ≤ N ≤50

???????1 ≤ K ≤2,000,000,000

???????1 ≤NFish ≤ 20

?

【樣例輸入】

6 8 1 5 3

0 2

2 1

1 0

0 5

5 1

1 4

4 3

3 5

1

3 0 5 1

?

【樣例輸出】

2

?

【樣例說明】

時(shí)刻	0	1	2	3
食人魚位置	0	5	1	0
路線一	1	2	0	5
路線二	1	4	3	5

【解題思路】

知識(shí)點(diǎn)：

圖鄰接矩陣上的乘法

圖的鄰接矩陣可以唯一地表示一張圖，并且有很多神奇的性質(zhì)。

首先，我們來看一下最簡(jiǎn)單的情況，一張N個(gè)點(diǎn)的無向無權(quán)圖。如果點(diǎn)a和點(diǎn)b連邊，那么鄰接矩陣G[a,b]=G[b,a]=1，否則都等于0。

考慮鄰接矩陣自乘，即G2=G*G(矩陣乘法)可以得出結(jié)論，G^k[a,b]就等同a到b經(jīng)過k-1個(gè)中間點(diǎn)也就是長度為k的路徑條數(shù)。

那么對(duì)于有重邊的圖，我們只需要把G[a,b]改為表示點(diǎn)a、b之間重邊的條數(shù)即可。

而對(duì)于有向圖的自環(huán)不需要特殊考慮。

對(duì)于無向圖的自環(huán)，我們通常是把G[a,a]加上2，這樣在計(jì)算Gk的時(shí)候這條邊就被算成2條不同的邊，如果只加上1，又會(huì)不滿足矩陣?yán)锼性睾偷扔谶厰?shù)兩倍的性質(zhì)。

考慮這個(gè)問題，假設(shè)沒有食人魚，那么這道題目就變成了上述所說的求由a到b長度為k的路徑條數(shù)，即求連接矩陣G^k[a,b]。

再考慮有食人魚的情況：

圖鄰接矩陣上的乘法有食人魚和沒有食人魚的區(qū)別就在于，前者的圖是不斷在變化，而后者的圖始終是不變的。

設(shè)Gi表示把與時(shí)刻i不能經(jīng)過的點(diǎn)相關(guān)的邊都去掉以后的圖。相乘同樣可以得到最終時(shí)刻的答案矩陣Gk*Gk-1*Gk-2....*G1。

那么這樣就是最優(yōu)解了嗎？

觀察題目數(shù)據(jù)范圍可以發(fā)現(xiàn)，2≤T≤4，2、3、4的最小公倍數(shù)為12，則最多沒12單位時(shí)間為一個(gè)周期，所以我們只用考慮12單位時(shí)間內(nèi)的各連接矩陣即可。

但是注意到k不一定是12的倍數(shù)，所以k mod 12也就是最后未滿一個(gè)周期的時(shí)間，我們可以單獨(dú)相乘，前面周期計(jì)算采用快速冪，這樣間復(fù)雜度為O(N2logK)

【源代碼】/pas

typearr=array[0..101,0..101]of longint; constpp=10000;var a,b:array[0..101]of longint; n,m,s,e,q:longint; t,c,d:arr; g:array[0..12]of arr;procedure ch(u,v:arr); var j,k,l:longint; beginfillchar(c,sizeof(c),0);for j:=1 to n dofor k:=1 to n dofor l:=1 to n doc[j,k]:=(c[j,k]+(u[j,l]*v[l,k])mod pp)mod pp; end;procedure dfs(y:longint); beginif y<1 then exit;dfs(y div 2);ch(c,c);if y mod 2=1 thench(c,d); end;procedure init; var i,j,k:Longint; x,y,r,l:longint; beginreadln(n,m,s,e,q);for i:=1 to m dobeginreadln(x,y);t[x+1,y+1]:=1;t[y+1,x+1]:=1;end;for i:=1 to 12 do g[i]:=t;readln(r);for i:=1 to r dobeginread(l);for j:=1 to l doread(b[j]);for j:=1 to 12 dofor k:=1 to n dog[j,k,b[(j mod l)+1]+1]:=0;end; end;procedure main; var i,j:longint; beginfillchar(c,sizeof(c),0);for i:=1 to n do c[i,i]:=1;for i:=1 to 12 doch(c,g[i]);d:=c;fillchar(c,sizeof(c),0);for i:=1 to n do c[i,i]:=1;dfs(q div 12);for i:=1 to q mod 12 doch(c,g[i]); end; begininit;main;writeln(c[s+1,e+1]); end.

轉(zhuǎn)載于:https://www.cnblogs.com/olahiuj/p/5781346.html

總結(jié)

以上是生活随笔為你收集整理的沼泽鳄鱼_SSL2511_矩阵乘法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。