1898: [Zjoi2005]Swamp 沼澤鱷魚

Time Limit:?5 Sec??Memory Limit:?64 MB
Submit:?1197??Solved:?661
[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

HINT

Source

?

俞華程論文上的題目。 首先我們得解決一個問題，如果沒有魚該怎么做，論文上已經寫了，是這樣做的。 我們先構造出一個鄰接矩陣G[0] 如果u和v相連， 那么G[0][u][v] = G[0][v][u] = 1 G[0]是指第0步的狀態 G[0]怎么轉移到G[1]？其實這個過程和floyde類似。floyde是f[i][j] = f[i][k] + f[k][j] 這里是 if(k->v可行） G[1][u][v] += G[0][k][v] 這很好理解，跟floyde有異曲同工之妙（自己的理解） 那么就可以用矩陣快速冪加速 這道題比上道題多了魚的限制，我們發現lcm(2,3,4)=12,也就是說每12步是一個周期，所以我們可以先把K/12的那部分矩陣快速冪掉，因為每12步后都是不變的，然后剩余的暴力乘上。 #include<bits/stdc++.h> using namespace std; const int N = 55, mod = 10000; int n, m, s, t, K, Fish; int f[N]; struct matrix {int g[N][N];void clr() { memset(g, 0, sizeof(g)); }void init() { for(int i = 1; i <= n; ++i) g[i][i] = 1; }} M[N]; matrix operator * (matrix &A, matrix &B) {matrix ret; ret.clr();for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) if(A.g[i][k])for(int j = 1; j <= n; ++j) if(B.g[k][j]) ret.g[i][j] = (ret.g[i][j] + A.g[i][k] * B.g[k][j]) % mod; return ret; } matrix operator ^ (matrix A, int t) {matrix ret; ret.clr(); ret.init();for(; t; t >>= 1, A = A * A) if(t & 1) ret = ret * A;return ret; } int main() {scanf("%d%d%d%d%d", &n, &m, &s, &t, &K); ++s; ++t;M[0].init();for(int i = 1; i <= m; ++i){int u, v; scanf("%d%d", &u, &v);++u; ++v;for(int j = 1; j <= 12; ++j)M[j].g[u][v] = M[j].g[v][u] = 1;}scanf("%d", &Fish);for(int i = 1; i <= Fish; ++i){int T; scanf("%d", &T);for(int j = 1; j <= T; ++j) scanf("%d", &f[j]), ++f[j];for(int j = 1; j <= 12; ++j) for(int k = 1; k <= n; ++k) M[j].g[k][f[j % T + 1]] = 0; }for(int i = 1; i <= 12; ++i) M[0] = M[0] * M[i];matrix ans;ans = M[0] ^ (K / 12);for(int i = 1; i <= K % 12; ++i) ans = ans * M[i];printf("%d\n", ans.g[s][t] % mod); return 0; } View Code

?

轉載于:https://www.cnblogs.com/19992147orz/p/6607913.html

總結

以上是生活随笔為你收集整理的bzoj 1898的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。