学步园

 一个矩阵乘法的问题, 迭代矩阵用二分的方法, 要注意只需考虑奇偶性, 所以用01矩阵就够了.
题目是从0开始计算, 所以迭代次数为t-1.

PS. 动态申请空间果然很慢, 还是模版好.
用new动态申请空间时:
Accepted 6960K 1063MS (没有delete)
Accepted 1860K 1235MS (加了delete)

使用静态二维数组+memcpy:
Accepted 360K 219MS

源码:

/*********************************

  matrix multiply.
  divide mat[]^n into (mat[]^(n/2))^2, the thought of dichotomy.

*********************************/

#include<iostream>
#include<string>
using namespace std;
const int maxn=100+5;

int n,t,len;
string str,name[maxn];
int a[maxn],r[maxn];

int find(){
	for(int i=0;i<len;++i){
		if(name[i]==str) return i;
	}
	name[len++]=str;
	return len-1;
}

void mul_matrix(int (*x)[maxn], int (*y)[maxn]){
	int i,j,k,tmp[maxn][maxn];
	for(i=0;i<n;++i)
		for(j=0;j<n;++j){
			tmp[i][j]=0;
			for(k=0;k<n;++k){
				tmp[i][j]+=x[i][k]*y[k][j];
				tmp[i][j]&=1;
			}
		}
	memcpy(x,tmp,sizeof(tmp));
}

void cal_matrix(int m,int (*x)[maxn]){
	int i,tmp[maxn][maxn];
	memset(tmp,0,sizeof(tmp));
	for(i=0;i<n;++i) tmp[i][i]=1;
	while(m){
		if(m&1) mul_matrix(tmp,x);
		mul_matrix(x,x);
		m>>=1;
	}
	memcpy(x,tmp,sizeof(tmp));
}


int main(){
	//freopen("1.txt","r",stdin);
	int i,j,k,tc,loc,to,res;
	int x[maxn][maxn],y[maxn][maxn];
	cin>>tc;
	while(tc--){
		res=0;
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		cin>>n>>t;
		len=0;
		for(i=0;i<n;++i){
			cin>>str;
			loc=find();
			cin>>a[loc]>>k;
			a[loc]&=1;
			for(j=0;j<k;++j){
				cin>>str;
				to=find();
				//x[loc][to]++;
				x[loc][to]=1;
			}
		}
		for(i=0;i<n;++i){
			//cout<<a[i]<<" ";
			x[i][i]=1-(x[i][i]&1);
		}
		cal_matrix(t-1,x);
/*
		for(i=0;i<n;++i)
		{
			for(j=0;j<n;++j)
				cout<<x[i][j]<<" ";
			cout<<endl;
		}
*/
		for(i=0;i<n;++i){
			r[i]=0;
			for(j=0;j<n;++j)
				r[i]+=a[j]*x[j][i];
			//cout<<r[i]<<" ";
			if(r[i]&1) res++;
		}
		printf("%d/n",res);


	}
	return 0;
}

/******************
1
5 2
a 234 4 b c d e
b 586 1 c
c 97 1 e
d 768 3 a e d
e 798 4 b e c a
******************/

这个矩阵幂的函数要收下了, 嗯嗯~