加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 1 1号城市上。这个可乐机器人有三种行为：停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图，在第 0 0秒时可乐机器人在 1 1号城市，问经过了 t t秒，可乐机器人的行为方案数是多少？
第一行输入两个正整数 N,M N,M, N N表示城市个数， M M表示道路个数。( 1≤N≤30 1≤N≤30, 0≤M≤100 0≤M≤100)
接下来M行输入 u,v u,v，表示 u,v u,v之间有一条道路。( 1≤u,v≤n 1≤u,v≤n)保证两座城市之间只有一条路相连。
最后输入时间 t t。
输出可乐机器人的行为方案数，答案可能很大，请输出对 2017 2017取模后的结果。
对于20%的数据，有 1<t≤1000 1<t≤1000 对于100%的数据，有 1<t≤106 1<t≤106。
矩阵快速幂优化DP~
用f[i][j][0/1]表示在i时刻，j点，1不爆炸，0已爆炸的方案数，那么f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]，f[i][j][1]=f[i-1][j][1]+f[i-1][k][1]（其中k表示与j相邻的点）。
然后，就T了QAQ
所以我们需要一些优化。
先看f[i][j][1]=f[i-1][j][1]+f[i-1][k][1]，如果我们假设i与自己相连，那么这个式子就是f[i][j][1]=f[i-1][k][1]，可以用矩阵快速幂来计算——
我们在a矩阵中记录图的联通性（注意这里a[i][i]=1），然后自乘t次，再与f[0][i][1]相乘即为答案。
然后，f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]等价于sum{f[i-1][j][1]}，由前面f[i][j][1]的求法可知它是个等比数列，求和公式一套就好了~
程序里面的f和g数组是学的Xiejiadong神犇的，相当于求矩阵的和，并没有DP的意思，这里可能容易混。
我在函数里面把v写成了y……所以一定要检查有没有变量用错的情况啊，尤其是u和v和y！
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define mod 2017 int n,m,t,x,y,f[31],g[31],ans; struct node{ int a[31][31]; }a,b; 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<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } node operator + (node u,node v) { node z; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) z.a[i][j]=u.a[i][j]+v.a[i][j]%mod; return z; } node operator * (node u,node v) { node z; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { z.a[i][j]=0; for(int k=1;k<=n;k++) z.a[i][j]=(z.a[i][j]+u.a[i][k]*v.a[k][j]%mod)%mod; } return z; } node mi(node u,int v) { node z; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) z.a[i][j]=i==j ? 1:0; for(;v;v>>=1,u=u*u) if(v&1) z=z*u; return z; } node sum(node u,int v) { node z; memset(z.a,0,sizeof(z.a)); if(!v) return z; if(v==1) return u; for(int i=1;i<=n;i++) z.a[i][i]=1; z=z+mi(u,v>>1);z=z*(sum(u,v>>1)); if(v&1) z=z+mi(u,v); return z; } int main() { n=read();m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),a.a[x][y]=a.a[y][x]=1; for(int i=1;i<=n;i++) a.a[i][i]=1; t=read();b=a;a=mi(a,t);g[1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i]=(f[i]+g[j]*a.a[i][j]%mod)%mod; for(int i=1;i<=n;i++) ans=(ans+f[i])%mod; b=sum(b,t-1); for(int i=1;i<=n;i++) b.a[i][i]=(b.a[i][i]+1)%mod; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i]=(f[i]+g[j]*b.a[i][j]%mod)%mod; for(int i=1;i<=n;i++) ans=(ans+f[i])%mod; printf("%d\n",ans); return 0; }
