P3758 [TJOI2017]可樂

---

這個題是利用了鄰接矩陣的性質

即：對于一個鄰接矩陣\(E\)，表示從\(E[i][j]\)到\(i\)到\(j\)路徑長度為1的方案數是多少。那么\(E^k[i][j]\)表示從\(i\)到\(j\)路徑長度為\(K\)

對這個題

對于走到其他城市，就可以直接使用鄰接矩陣想乘

而對于原地不動，我們可以理解成向當前的城市添加一個自環就行了

然后對于自爆，我們就是前一秒的方案數都存下來，我們就可以設一個零號城市，所有城市都可以到他，然后這個城市無法到達其他城市

然后就可以愉快的快速冪了

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> const int maxn=110; const int RQY=2017; struct node {int n,m;int map[maxn][maxn];node (int n=0,int m=0){memset(map,0,sizeof(map));}node operator * (const node &a)const {node res;res.n=n,res.m=a.m;for(int i=0;i<=n;i++)for(int j=0;j<=res.m;j++)for(int k=0;k<=m;k++)res.map[i][j]=(res.map[i][j]+map[i][k]*a.map[k][j])%RQY;return res;} }; node A,C; node kasumi(node b,int t) {node Res=b;t--;while(t){if(t&1)Res=Res*b;t>>=1;b=b*b;}return Res; } int main() {int n,m,T;scanf("%d%d",&n,&m);A.n=n;A.m=n;for(int i=0;i<=n;i++) A.map[i][i]=A.map[i][0]=1;int a,b;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);A.map[a][b]++;A.map[b][a]++;}scanf("%d",&T);C=kasumi(A,T);int tot=0;for(int i=0;i<=C.m;i++)tot=(tot+C.map[1][i])%RQY;printf("%d",tot); }

轉載于:https://www.cnblogs.com/Lance1ot/p/9612519.html

總結

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

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