#include <cstdio> typedef long long LL; const int MAXTOL=25000005,MAXN=1005; LL p=1000000007LL,q=3000000019LL,curr_hasz,x,y,hasz_wzo,pp; int T[MAXN][MAXN],siz[MAXN]; int G[MAXTOL][2]; int n,m,l,mp,d,pos,s,si; int main() { pp=p; scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) { scanf("%d", &l); siz[i]=l; for(int j=0; j<l; ++j) scanf("%d", &T[i][j]); } for(int i=0; i<m; ++i) { scanf("%lld", &x); x=(x+y)*p; x%=q; y=x; pp*=p; pp%=q; } hasz_wzo=y; G[0][0]=1; if(hasz_wzo==p) { printf("1"); return 0; } mp=m-1; d=2; s=1; while(1) { pos=0; si=0; for(int i=0; i<s; ++i) si+=siz[G[i][(d&1)]]; if(si>=MAXTOL) break; for(int i=0; i<s; ++i) { for(int j=0; j<siz[G[i][(d&1)]]; ++j) { G[pos++][((1+d)&1)]=T[G[i][(d&1)]][j]; //printf("%d ", T[G[i][(d&1)]][j]); curr_hasz+=T[G[i][(d&1)]][j]; curr_hasz*=p; curr_hasz%=q; if(pos>=m) { curr_hasz-=((pp*G[pos-m-1][((1+d)&1)])%q); curr_hasz+=q; curr_hasz%=q; } if(curr_hasz == hasz_wzo && pos>=mp) { printf("%d", d+1); return 0; } } } ++d; s=si; curr_hasz=0LL; } printf("-1"); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <cstdio> typedef long long LL; const int MAXTOL=25000005,MAXN=1005; LL p=1000000007LL,q=3000000019LL,curr_hasz,x,y,hasz_wzo,pp; int T[MAXN][MAXN],siz[MAXN]; int G[MAXTOL][2]; int n,m,l,mp,d,pos,s,si; int main() { pp=p; scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) { scanf("%d", &l); siz[i]=l; for(int j=0; j<l; ++j) scanf("%d", &T[i][j]); } for(int i=0; i<m; ++i) { scanf("%lld", &x); x=(x+y)*p; x%=q; y=x; pp*=p; pp%=q; } hasz_wzo=y; G[0][0]=1; if(hasz_wzo==p) { printf("1"); return 0; } mp=m-1; d=2; s=1; while(1) { pos=0; si=0; for(int i=0; i<s; ++i) si+=siz[G[i][(d&1)]]; if(si>=MAXTOL) break; for(int i=0; i<s; ++i) { for(int j=0; j<siz[G[i][(d&1)]]; ++j) { G[pos++][((1+d)&1)]=T[G[i][(d&1)]][j]; //printf("%d ", T[G[i][(d&1)]][j]); curr_hasz+=T[G[i][(d&1)]][j]; curr_hasz*=p; curr_hasz%=q; if(pos>=m) { curr_hasz-=((pp*G[pos-m-1][((1+d)&1)])%q); curr_hasz+=q; curr_hasz%=q; } if(curr_hasz == hasz_wzo && pos>=mp) { printf("%d", d+1); return 0; } } } ++d; s=si; curr_hasz=0LL; } printf("-1"); } |