矩阵优化dp
** 注意：矩阵乘法没有交换律 **
思路：类比P2151hh去散步
代码特点在一维的答案矩阵
1.矩阵优化两点间方案数不必赘述
2.注意2，3，4可以办到以他们的lcm为周期，正是因为如此我们可以矩阵加速（这样我们就可以化动为静，矩阵乘法了）
3.一维初始矩阵（一维邻接矩阵+第二个矩阵取交集）注意当前鳄鱼的位置与我们下一次走并无关，他们正好搓了一位，要小心
4.再次强调：矩阵乘法没有交换律：因此，我们在构造转移矩阵时要从2开始到12，再乘1（这里指的是矩阵）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,S,E,k,t,mod=10000;
int record[20][60],Map[60][60];
struct M{
int m[60][60];
M(){
memset(m,0,sizeof(m));
}
M operator *(const M &a)const {//重载定义矩阵乘法
M ret;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
ret.m[i][j]=(ret.m[i][j]+m[i][k]%mod*a.m[k][j]%mod)%mod;
return ret;
}
}c[20],e,A;
inline void build(){//构造转移矩阵
for(int i=1;i<=n;++i)e.m[i][i]=1;
for(int i=1;i<=12;++i){
for(int j=1;j<=n;++j){
for(int k=1;k<=n;++k){
if(Map[j][k]&&(!record[i][j]))c[i].m[k][j]=1;
}
}
}
for(int i=2;i<=12;i++)e=e*c[i];//矩乘没有交换律
e=e*c[1];//因为我们的第二个矩阵跟第一步有关，所以先乘2矩阵
}
inline void power(M &a,M &b,int k){
while(k){
if(k&1)a=a*b;
b=b*b;
k>>=1;
}
}//矩阵快速幂
inline void solve(){//极其繁琐需要头脑冷静
if(k==1){printf("%d",Map[S][E]);return ;}
for(int i=1;i<=n;++i)if(Map[S][i]&&c[2].m[S][i])A.m[S][i]=1;//先跟第二矩阵取交集，表示走第一步--此处表示构造初始矩阵
if(k<=12)for(int i=3;i<=k+1;++i)A=A*c[i%12];//此处分类讨论
else {//因为初始矩阵的存在，我们已经走了一步
for(int i=3;i<=12;++i)A=A*c[i];//所以在这里我们先暴力走一遍
A=A*c[1];//注意不能交换律
power(A,e,(k/12)-1);//先乘了一遍所以-1
for(int i=2;i<=(k-12)%12+1;++i)A=A*c[i];//最后再o再
}
printf("%d",A.m[S][E]);
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&S,&E,&k);
S++,E++;//加1比较顺我的思路，下面的加1同
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
++x,++y;
Map[x][y]=1;
Map[y][x]=1;
}
scanf("%d",&t);
for(int i=1;i<=t;++i){
int num;
scanf("%d",&num);
for(int j=1;j<=num;++j){
int x;
scanf("%d",&x);
int k=j;
x++;
while(k<=12){
record[k][x]=1;
k+=num;
}//12一循环
}
}
build();
solve();
return 0;
}