Posted on 2010-01-30 03:17
Uriel 閱讀(586)
評論(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;
}