#include<cstdio> #include<cstring> #include<map> using namespace std; #define MAXN 105 struct matrix { int m[MAXN][MAXN]; }; int n; void debug(matrix a) { printf("\n"); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) printf("%d ",a.m[i][j]); printf("\n"); } } matrix multi(const matrix &a,const matrix &b) { matrix ans; memset(&ans,0,sizeof(ans)); for(int i=0;i<n;i++) for(int k=0;k<n;k++) if(a.m[i][k]) { for(int j=0;j<n;j++) { ans.m[i][j]+=a.m[i][k]*b.m[k][j]; ans.m[i][j]%=2; } } return ans; } matrix pow(matrix a,int k) { matrix ans; memset(&ans,0,sizeof(ans)); for(int i=0;i<n;i++) ans.m[i][i]=1; while(k) { if(k&1) ans=multi(ans,a); a=multi(a,a); k>>=1; } return ans; } struct node { char name[25]; bool operator < (const node &a) const { return strcmp(name,a.name)>0; } }; map<node,int> rec; int main() { matrix a,b; node t; int cas,k,x,y; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&k); memset(&a,0,sizeof(a)); memset(&b,0,sizeof(b)); rec.clear(); int cnt=1; for(int i=0;i<n;i++) { scanf("%s",t.name); if(!rec[t]) rec[t]=cnt++; int idx=rec[t]; scanf("%d%d",&x,&y); b.m[0][idx-1]=x%2; while(y--) { scanf("%s",t.name); if(!rec[t]) rec[t]=cnt++; int idy=rec[t]; a.m[idx-1][idy-1]=1; } } for(int i=0;i<n;i++) a.m[i][i]++; //debug(b); //debug(a); a=pow(a,k-1); //debug(a); int ans=0,sum; for(int i=0;i<n;i++) { sum=0; for(int j=0;j<n;j++) { sum+=b.m[0][j]*a.m[j][i]; //printf("%d*%d ",b.m[0][j],a.m[j][i]); } //printf("\n"); if(sum%2) ans++; } printf("%d\n",ans); } return 0; } |
Double click to view unformatted code.