1898: [Zjoi2005]Swamp 沼澤鱷魚

Time Limit:?5 Sec??Memory Limit:?64 MB
Submit:?1082??Solved:?602
[Submit][Status][Discuss]

Description

潘塔納爾沼澤地號(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)然不能遭到食人魚的攻擊）。

Input

輸入文件共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ù)P0和P1，食人魚從P0到P1，從P1到P0，……；? 如果T＝3，接下來有3個(gè)數(shù)P0，P1和P2，食人魚從P0到P1，從P1到P2，從P2到P0，……；? 如果T＝4，接下來有4個(gè)數(shù)P0，P1，P2和P3，食人魚從P0到P1，從P1到P2，從P2到P3，從P3到P0，……。豆豆出發(fā)的時(shí)候所有食人魚都在自己路線上的P0位置，請(qǐng)放心，這個(gè)位置不會(huì)是Start石墩。

Output

輸出路線的種數(shù)，因?yàn)檫@個(gè)數(shù)可能很大，你只要輸出該數(shù)除以10000的余數(shù)就行了。 【約定】? 1 ≤ N ≤ 50 ? 1 ≤ K ≤ 2,000,000,000 ? 1 ≤ NFish ≤ 20

Sample Input

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

Sample Output

2

【樣例說明】
時(shí)刻 0 1 2 3
食人魚位置 0 5 1 0
路線一 1 2 0 5
路線二 1 4 3 5

---

元旦集訓(xùn)講課時(shí)想出來了 bingo 沒有食人魚不是裸題嗎，用一個(gè)向量表示從s到1..N的距離，然后不停乘鄰接矩陣行了，當(dāng)然快速冪 有食人魚，發(fā)現(xiàn)食人魚最多十二個(gè)鄰接矩陣一循環(huán)，處理出12個(gè)作為1個(gè)然后快速冪行了 怎么處理呢？ 假設(shè)食人魚在j時(shí)刻到達(dá)x這個(gè)點(diǎn)，那么j時(shí)刻的鄰接矩陣x這一列全是0，因?yàn)樗笙乱粋€(gè)矩陣的貢獻(xiàn)上不能有x這一列貢獻(xiàn)的 注意： 一開始s和t忘+1了....然后... #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=52,MOD=1e4; typedef long long ll; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int n,m,s,t,k,x,y,fish,f[15]; struct Mat{int a[N][N];Mat(){memset(a,0,sizeof(a));}void ini(){for(int i=1;i<=n;i++) a[i][i]=1;} }g[15],ans; inline Mat operator *(Mat A,Mat B){Mat C;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++) if(A.a[i][k])for(int j=1;j<=n;j++) if(B.a[k][j])C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;return C; } inline Mat operator ^(Mat A,int k){Mat ans;ans.ini();for(;k;k>>=1,A=A*A)if(k&1) ans=ans*A;return ans; } void print(Mat A){puts("hiMat");for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) printf("%d ",A.a[i][j]);puts("");} } int main(){//freopen("in.txt","r",stdin);n=read();m=read();s=read()+1;t=read()+1;k=read();for(int i=1;i<=m;i++){x=read()+1;y=read()+1;for(int j=1;j<=12;j++) g[j].a[x][y]=g[j].a[y][x]=1;}fish=read();for(int i=1;i<=fish;i++){int T=read();for(int j=1;j<=T;j++) f[j]=read()+1;for(int j=1;j<=12;j++)for(int k=1;k<=n;k++) g[j].a[k][f[j%T+1]]=0;}g[0].ini();for(int i=1;i<=12;i++) g[0]=g[0]*g[i];ans=g[0]^(k/12);for (int i=1;i<=k%12;i++) ans=ans*g[i];printf("%d",ans.a[s][t]); }

?

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

總結(jié)

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

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