傳送門

Description

加里敦星球的人們特別喜歡喝可樂。因而，他們的敵對星球研發出了一個可樂機器人，并且

放在了加里敦星球的1號城市上。這個可樂機器人有三種行為：停在原地，去下一個相鄰的

城市，自爆。它每一秒都會隨機觸發一種行為。現在給出加里敦星球城市圖，在第0秒時可

樂機器人在1號城市，問經過了t秒，可樂機器人的行為方案數是多少？

Solution

蒟蒻\(PaperCloud\)終于\(bzoj\)百題祭啦

方案數=鄰接矩陣^t

自爆？建一個虛節點，所有點連向它即可。

留在原地？自己向自己連邊就可以了

Code?

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline int read() {int 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<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } #define mod 2017 #define reg register int N,M,u,v,T; struct matrix {int a[35][35],size;matrix(int _n=0,int _o=0):size(_n){memset(a,0,sizeof a);if(_o)for(reg int i=0;i<=size;i++) a[i][i]=1;}matrix operator *(const matrix& b)const{matrix C(size);for(int i=0;i<=size;i++)for(int j=0;j<=size;j++)for(int k=0;k<=size;k++) C.a[i][j]+=(a[i][k]*b.a[k][j])%mod;return C;} }; matrix fpow(matrix x,int m){matrix ret(N,1);for(;m;x=x*x,m>>=1) if(m&1) ret=ret*x;return ret; } int main() {N=read();M=read();register int i;matrix pac(N,1);for(i=1;i<=N;++i) pac.a[i][0]++;for(i=1;i<=M;++i) u=read(),v=read(),pac.a[u][v]++,pac.a[v][u]++;pac=fpow(pac,read());register int ans=0;for(i=0;i<=N;++i) (ans+=pac.a[1][i])%=mod;return 0*printf("%d\n",ans); }

---

Blog來自PaperCloud，未經允許，請勿轉載，TKS！

轉載于:https://www.cnblogs.com/PaperCloud/p/10244301.html

總結

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

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