POJ 1977 构造矩阵乘法

题目大意：

有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|

到底代表什么意思呢？

我们可以这么看:

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;
}