1977.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"string.h"

char m[30][100][100];
int n,t,v[100];
char name[100][100][100];
char nm[100][100];
int s[100];
char ans[100][100];
char temp[100][100];

void multiply(char a[100][100],char b[100][100],char c[100][100])
{
	int i,j,k;
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{
		c[i][j]=0;
		for(k=0;k<n;k++)
			c[i][j]+=a[i][k]*b[k][j];
		c[i][j]%=2;
	}
	return;
}
void init()
{
	int i,j,k;
	cin>>n>>t;

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		m[0][i][j]=0;
	for(i=0;i<n;i++)
		m[0][i][i]++;
	
	for(i=0;i<n;i++)
	{
		cin>>nm[i];
		cin>>v[i];
		v[i]%=2;
		cin>>s[i];
		for(j=0;j<s[i];j++)
			cin>>name[i][j];
	}

	for(i=0;i<n;i++)
	for(j=0;j<s[i];j++)
	{
		for(k=0;k<n;k++)
			if(strcmp(nm[k],name[i][j])==0)break;
		m[0][i][k]++;
		m[0][i][k]%=2;
	}

	t--;
	for(i=1;(1<<i)<=t;i++)
	{
		multiply(m[i-1],m[i-1],m[i]);
	}

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		ans[i][j]=0;
	
	for(i=0;i<n;i++)
		ans[i][i]=1;
	
	for(i=0;t;i++)
	{
		if(t%2)
		{
			multiply(ans,m[i],temp);
			for(j=0;j<n;j++)
			for(k=0;k<n;k++)
				ans[j][k]=temp[j][k];
		}
		t/=2;
	}
}

		

int main()
{
	int cas,i,j,an[100],answer;
	cin>>cas;
	while(cas--)
	{
		init();
		for(i=0;i<n;i++)
		{
			an[i]=0;
			for(j=0;j<n;j++)
				an[i]+=v[j]*ans[j][i];
			an[i]%=2;
		}
		answer=0;
		for(i=0;i<n;i++)
			answer+=an[i];
		cout<<answer<<endl;
	}
	return 0;
}