Luogu 3758 [TJOI2017]可樂（有向圖鄰接矩陣冪的意義 矩陣快速冪）
題目描述
加里敦星球的人們特別喜歡喝可樂。因而，他們的敵對星球研發(fā)出了一個可樂機器人，并且放在了加里敦星球的1號城市上。這個可樂機器人有三種行為： 停在原地，去下一個相鄰的城市，自爆。它每一秒都會隨機觸發(fā)一種行為。現(xiàn) 在給加里敦星球城市圖，在第0秒時可樂機器人在1號城市，問經(jīng)過了t秒，可樂機器人的行為方案數(shù)是多少？
輸入輸出格式
輸入格式：
第一行輸入兩個正整數(shù)況N,M，N表示城市個數(shù)，M表示道路個數(shù)。（1 <= N <=30,0 < M < 100)
接下來M行輸入u,v，表示u，v之間有一條道路。（1<=u,v <= n)保證兩座城市之間只有一條路相連。
最后輸入入時間t
輸出格式：
輸出可樂機器人的行為方案數(shù)，答案可能很大，請輸出對2017取模后的結(jié)果。
輸入輸出樣例
說明
【樣例解釋】
1 ->爆炸
1 -> 1 ->爆炸
1 -> 2 ->爆炸
1 -> 1 -> 1
1 -> 1 -> 2
1 -> 2 -> 1
1 -> 2 -> 2
1 -> 2 -> 3
【數(shù)據(jù)范圍】
對于20%的pn，有1 < t ≤ 1000
對于100%的pn，有1 < t ≤ 10^6。
解題思路：
前置技能：有向圖鄰接矩陣冪的意義 不懂的戳這里：http://www.rzrgm.cn/Dxy0310/p/9838613.html
題目所求的行為方案數(shù)可以理解為到每一個可到達(dá)的點的方案數(shù)的總和，而鄰接矩陣的冪正好有這樣的性質(zhì)，
用鄰接矩陣$A$表示原圖的連通關(guān)系，那么$A^k$中的$（i,j）$上的數(shù)值表示從$i$到$j$經(jīng)過$k$的路徑方案總數(shù)。
那么$\sum\limits_{i=1}^{n} A[1][i]$就是答案的一部分，接下來考慮原地停留的問題，其實原地停留就相當(dāng)于每個點都有一條自己連自己的邊構(gòu)成自環(huán)，將$A_{i,i}$賦值為$1$即可，再考慮自爆的情況，因為自爆之后便沒有狀態(tài)了，所以可以將自爆看成一個新的城市$n+1$,由于可能在每一個點上自爆，所以由每一個點向點$n+1$連一條有向邊，由于自爆后沒狀態(tài)，所以點$n+1$的出邊應(yīng)該為$0$。
至此題目就轉(zhuǎn)化成了建立圖的鄰接矩陣$A$，并計算$A^k$，用矩陣快速冪即可。
代碼：
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define INF 0x3f3f3f3f #define maxn 39 #define maxm inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();} return x*f; } int mp[maxn][maxn],B[maxn][maxn],C[maxn][maxn]; int n,m,k,ans,tot,cnt,t,p; void Martix_mul(int A[maxn][maxn],int B[maxn][maxn]) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) C[i][j]+=A[i][k]*B[k][j],C[i][j]%=p; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) A[i][j]=C[i][j],C[i][j]=0; } void Quick_mul(int b) { while(b) { if(b&1) Martix_mul(B,mp); Martix_mul(mp,mp); b>>=1; } } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read(),m=read(),p=2017; for(int i=1;i<=m;i++) { int x=read(),y=read(); mp[x][y]=mp[y][x]=1; } for(int i=1;i<=n+1;i++) { mp[i][i]=1; mp[i][n+1]=1; B[i][i]=1; } t=read(); ++n; Quick_mul(t); for(int i=1;i<=n;i++) ans+=B[1][i],ans%=p; printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; }
浙公網(wǎng)安備 33010602011771號