Poj Solution 1977

http://poj.org/problem?id=1977

#include<iostream>
#include"string.h"
using namespace std;

char m[30][100][100];
int n,t,v[100];
char name[100][100][100];
char nm[100][100];
int s[100];
char ans[100][100];
char temp[100][100];

void multiply(char a[100][100],char b[100][100],char c[100][100])
{
    int i,j,k;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        c[i][j]=0;
        for(k=0;k<n;k++)
            c[i][j]+=a[i][k]*b[k][j];
        c[i][j]%=2;
    }
    return;
}
void init()
{
    int i,j,k;
    cin>>n>>t;

    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        m[0][i][j]=0;
    for(i=0;i<n;i++)
        m[0][i][i]++;
    
    for(i=0;i<n;i++)
    {
        cin>>nm[i];
        cin>>v[i];
        v[i]%=2;
        cin>>s[i];
        for(j=0;j<s[i];j++)
            cin>>name[i][j];
    }

    for(i=0;i<n;i++)
    for(j=0;j<s[i];j++)
    {
        for(k=0;k<n;k++)
            if(strcmp(nm[k],name[i][j])==0)break;
        m[0][i][k]++;
        m[0][i][k]%=2;
    }

    t--;
    for(i=1;(1<<i)<=t;i++)
    {
        multiply(m[i-1],m[i-1],m[i]);
    }

    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        ans[i][j]=0;
    
    for(i=0;i<n;i++)
        ans[i][i]=1;
    
    for(i=0;t;i++)
    {
        if(t%2)
        {
            multiply(ans,m[i],temp);
            for(j=0;j<n;j++)
            for(k=0;k<n;k++)
                ans[j][k]=temp[j][k];
        }
        t/=2;
    }
}

        

int main()
{
    int cas,i,j,an[100],answer;
    cin>>cas;
    while(cas--)
    {
        init();
        for(i=0;i<n;i++)
        {
            an[i]=0;
            for(j=0;j<n;j++)
                an[i]+=v[j]*ans[j][i];
            an[i]%=2;
        }
        answer=0;
        for(i=0;i<n;i++)
            answer+=an[i];
        cout<<answer<<endl;
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *