Posted on 2010-01-30 03:17
Uriel 阅读(552)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
递归 & 分治
ECUST寒假第二次练习赛的题，最后1h都在努力，结果还是没搞定，赛后纠结了好一会儿终于过了，原来矩阵乘法某处写错了，sample出了就没检查。。菜啊，完全离不开模板。。连个二分矩阵连乘都写不好。。
转移矩阵是(A+I)%2,A就是按题目所给条件构造的矩阵，类似邻接矩阵。。最后用T(初始行向量)左乘该结果，构造时我完全没想字符串hash的事。。直接暴力找了。。
注意：矩阵乘t-1次，相乘过程中不断%2，最后值为1计数
/**//*Problem: 1977 User: Uriel
Memory: 564K Time: 782MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 110
typedef int M[MAXN][MAXN];
struct person
{
char name[25],fav[MAXN][25];
int nfav;
int ori;
};
person P[MAXN];
int n,baker[MAXN],matrix[MAXN][MAXN],O[MAXN][MAXN],cse,t,res;
void copy(M x,M y)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
x[i][j]=y[i][j];
}
}
return ;
}
void mu(M x,M y)
{
int i,j,k,t;
M c;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
t=0;
for(k=0;k<n;k++)
{
if(x[i][k] && y[k][j])
{
t=(t+x[i][k]*y[k][j])%2;
}
}
c[i][j]=t;
}
}
copy(x,c);
return ;
}
void Cal(M a,int k)
{
if(k==1)
{
copy(a,O);
return ;
}
Cal(a,k/2);
mu(a,a);
if(k & 1)
{
mu(a,O);
}
}
int main()
{
int i,j,k;
scanf("%d",&cse);
while(cse--)
{
scanf("%d %d",&n,&t);
for(i=0;i<n;i++)
{
getchar();
scanf("%s",P[i].name);
scanf("%d %d",&P[i].ori,&P[i].nfav);
baker[i]=P[i].ori%2;
for(j=0;j<P[i].nfav;j++)
{
getchar();
scanf("%s",&P[i].fav[j]);
}
}
memset(O,0,sizeof(O));
for(i=0;i<n;i++)
{
O[i][i]=1;
}
for(i=0;i<n;i++)
{
for(j=0;j<P[i].nfav;j++)
{
for(k=0;k<n;k++)
{
if(strcmp(P[i].fav[j],P[k].name)==0)
{
break;
}
}
O[i][k]=(O[i][k]+1)%2;
}
}
Cal(matrix,t-1);
res=0;
for(i=0;i<n;i++)
{
int tmp=0 ;
for(j=0;j<n;j++)
{
tmp=(tmp+baker[j]*matrix[j][i])%2;
}
if(tmp)res++;
}
printf("%d\n",res);
}
// system("PAUSE");
return 0;
}