可以发现，如果没有鳄鱼，那么就是裸地一道题，但是可以发现鳄鱼最多每12次重复，那么就少于12的那部分dp，其他的就矩阵乘法就行了
PS：第一次吧矩阵乘法AC了好开心QAQ
CODE：
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#define mod 10000#define maxn 60using namespace std;struct mat{ int n,m,a[maxn][maxn]; mat(){n=m=0;memset(a,0,sizeof(a));} int I(int _x){n=m=_x;for (int i=1;i<=n;i++) a[i][i]=1;}};mat operator *(const mat &x,const mat &y){ mat ans; ans.n=x.n; ans.m=y.m; for (int i=1;i<=ans.n;i++) for (int j=1;j<=ans.m;j++) for (int k=1;k<=x.m;k++){ ans.a[i][j]+=x.a[i][k]*y.a[k][j]; ans.a[i][j]%=mod; } return ans;}mat power(mat x,int y){ mat ans;ans.I(x.n); for (;y;y>>=1){ if (y&1) ans=ans*x; x=x*x; } return ans;}int n,m,s,e,fn,ti;bool b[60][60];int a[20][7],t[60],f[60][60][15];int main(){ scanf("%d%d%d%d%d",&n,&m,&s,&e,&ti); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d
",&x,&y); x++;y++; b[x][y]=b[y][x]=1; } scanf("%d",&fn); for (int i=1;i<=fn;i++) { scanf("%d",&t[i]); for (int j=1;j<=t[i];j++) {scanf("%d",&a[i][j]);a[i][j]++; } } for (int i=1;i<=n;i++) f[i][i][0]=1; for (int i=1;i<=12;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++){ for (int l=1;l<=n;l++) if (f[j][l][i-1]&&b[l][k]) (f[j][k][i]+=f[j][l][i-1])%=mod; for (int l=1;l<=fn;l++) if (a[l][i%t[l]+1]==k) {f[j][k][i]=0;} } mat x,y; x.n=x.m=y.n=y.m=n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) x.a[i][j]=f[i][j][12]; x=power(x,ti/12); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) y.a[i][j]=f[i][j][ti%12]; x=x*y; printf("%d",x.a[s+1][e+1]); return 0;} |