BZOJ 1898: [Zjoi2005]Swamp 沼澤鱷魚 [矩陣乘法]

1898: [Zjoi2005]Swamp 沼澤鱷魚

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

Description

潘塔納爾沼澤地號稱世界上最大的一塊濕地，它地位于巴西中部馬托格羅索州的南部地區。每當雨季來臨，這里碧波蕩漾、生機盎然，引來不少游客。為了讓游玩更有情趣，人們在池塘的中央建設了幾座石墩和石橋，每座石橋連接著兩座石墩，且每兩座石墩之間至多只有一座石橋。這個景點造好之后一直沒敢對外開放，原因是池塘里有不少危險的食人魚。豆豆先生酷愛冒險，他一聽說這個消息，立馬趕到了池塘，想做第一個在橋上旅游的人。雖說豆豆愛冒險，但也不敢拿自己的性命開玩笑，于是他開始了仔細的實地勘察，并得到了一些驚人的結論：食人魚的行進路線有周期性，這個周期只可能是2，3或者4個單位時間。每個單位時間里，食人魚可以從一個石墩游到另一個石墩。每到一個石墩，如果上面有人它就會實施攻擊，否則繼續它的周期運動。如果沒有到石墩，它是不會攻擊人的。借助先進的儀器，豆豆很快就摸清了所有食人魚的運動規律，他要開始設計自己的行動路線了。每個單位時間里，他只可以沿著石橋從一個石墩走到另一個石墩，而不可以停在某座石墩上不動，因為站著不動還會有其它危險。如果豆豆和某條食人魚在同一時刻到達了某座石墩，就會遭到食人魚的襲擊，他當然不希望發生這樣的事情。現在豆豆已經選好了兩座石墩Start和End，他想從Start出發，經過K個單位時間后恰好站在石墩End上。假設石墩可以重復經過（包括Start和End），他想請你幫忙算算，這樣的路線共有多少種（當然不能遭到食人魚的攻擊）。

Input

輸入文件共M + 2 + NFish行。第一行包含五個正整數N，M，Start，End和K，分別表示石墩數目、石橋數目、Start石墩和End石墩的編號和一條路線所需的單位時間。石墩用0到N–1的整數編號。第2到M + 1行，給出石橋的相關信息。每行兩個整數x和y，0 ≤ x, y ≤ N–1，表示這座石橋連接著編號為x和y的兩座石墩。第M + 2行是一個整數NFish，表示食人魚的數目。第M + 3到M + 2 + NFish行，每行給出一條食人魚的相關信息。每行的第一個整數是T，T = 2，3或4，表示食人魚的運動周期。接下來有T個數，表示一個周期內食人魚的行進路線。? 如果T＝2，接下來有2個數P0和P1，食人魚從P0到P1，從P1到P0，……；? 如果T＝3，接下來有3個數P0，P1和P2，食人魚從P0到P1，從P1到P2，從P2到P0，……；? 如果T＝4，接下來有4個數P0，P1，P2和P3，食人魚從P0到P1，從P1到P2，從P2到P3，從P3到P0，……。豆豆出發的時候所有食人魚都在自己路線上的P0位置，請放心，這個位置不會是Start石墩。

Output

輸出路線的種數，因為這個數可能很大，你只要輸出該數除以10000的余數就行了。 【約定】? 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

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

---

元旦集訓講課時想出來了 bingo

沒有食人魚不是裸題嗎，用一個向量表示從s到1..N的距離，然后不停乘鄰接矩陣行了，當然快速冪

有食人魚，發現食人魚最多十二個鄰接矩陣一循環，處理出12個作為1個然后快速冪行了

怎么處理呢？

假設食人魚在j時刻到達x這個點，那么j時刻的鄰接矩陣x這一列全是0，因為他要求下一個矩陣的貢獻上不能有x這一列貢獻的

注意：

一開始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]);
}

?