学步园

题目大意：

有N个人，手上有Ai个标记，该人可以向指定的K个人添加标记（自己标记不会少）。

当该人手上有奇数个标记的时候，拥有投票权。问，最后有多少人手中的票为奇数个。

思路。以输入样例一为例：

初始状态矩阵:A=|210|

状态转移矩阵为：

     |111|

B=|001|

     |100|

于是乎第一轮结束后的状态：（A*B+A）

第二轮结束后的状态为：       （A*B+A）*B+（A*B+A）=> A*(B+E)*B+A*(B+E)=>A*(B+E)^2;

同样第三轮结束后:A*(B+E)^3

这样就是规律了；

另外还有注意的一点就是题中说当为奇数的时候有投票权，偶数没有投票权。

我们看看下面这个矩阵

|AB| * | EF |  = | A*Ｅ+B*G  A*F+B*H |

           |GH|

到底代表什么意思呢？

我们可以这么看:

1有Ａ次投票机会，每次机会分别投给1Ｅ票，2Ｇ票。

2有B 次投票机会，每次机会分别投给1F票，2H票。

这样1得到的票为A*E+B*G

可以发现当ABEFGH中为偶数的时候，都是没有用的。

所以直接%2是正确的。再者利用了矩阵的结合律。这么分析完，敲敲就AC了。

发现我的代码可以rank10诶~哈哈

#include<iostream>
#include<string.h>
#include<map>
#define MAXN 222
using namespace std;

typedef short ll;
struct node
{
 	   ll ma[MAXN][MAXN];
 	   void init(){
	   		memset(ma,0,sizeof(ma));
	   }
}res,temp,L;
int allocp;
void init()
{
 	 allocp=0;
 	 res.init();
 	 temp.init();
 	 L.init();
 	 for( int i=0;i<MAXN;i++ )
 	 	  res.ma[i][i]=1;
}

void set_Matrix()
{
 	 for( int i=0;i<allocp;i++ )
 	 	  temp.ma[i][i]++;
}

node matriXmult( node a,node b )
{
 	 node c;
 	 memset( c.ma,0,sizeof(c.ma) );
 	 for( int i=0;i<allocp;i++ )
 	 for( int k=0;k<allocp;k++ )
 	 if( a.ma[i][k] )
 	 for( int j=0;j<allocp;j++ )
 	 	  c.ma[i][j]+=a.ma[i][k]*b.ma[k][j];
 	 for( int i=0;i<allocp;i++ )
 	 for( int j=0;j<allocp;j++ )
 	 	  c.ma[i][j]%=2;
 	 return c;
}

void matrix_Power( int t )
{
 	 for( int i=0;i<31;i++ )
 	 {
	  	  if( t&(1<<i) )
	  	  	  res=matriXmult(res,temp);
	  	  temp=matriXmult(temp,temp);
	 }
}

int main()
{
 	int T,n,t,mark,list;
 	string str1,str2;
 	cin>>T;
 	while( T-- )
 	{
	 	   init();
	 	   map<string,int>map;
	 	   map.clear();
	 	   cin>>n>>t;
	 	   while( n-- )
	 	   {
	 	   		  cin>>str1;
	 	   		  if( map.find(str1)==map.end() )
	 	   		  	  map[str1]=allocp++;
	 	   		  cin>>mark>>list;
	 	   		  L.ma[0][map[str1]]=mark;
	 	   		  for( int i=0;i<list;i++ )
	 	   		  {
	 	   		  	   cin>>str2;
	 	   		  	   if( map.find(str2)==map.end() )
	 	   		  	   	   map[str2]=allocp++;
	 	   		  	   temp.ma[map[str1]][map[str2]]++;
			   	  }
   		   }
   		   t--;
   		   set_Matrix();
   		   matrix_Power(t);
   		   node kk;
   		   kk.init();
   		   for( int i=0;i<1;i++ )
   		   for( int j=0;j<allocp;j++ )
   		   for( int k=0;k<allocp;k++ )
   		   		kk.ma[i][j]+=L.ma[i][k]*res.ma[k][j];
   		   int sum=0;
   		   for( int i=0;i<allocp;i++ )
   		   		sum+=( kk.ma[0][i]%2 );
   		   cout<<sum<<endl;
  	}
 	return 0;
}