hdu2276Kiki & Little Kiki 2(矩阵) - c++编程基础

题意：给出n个灯，这n个灯成一个圆环，求m次变换每个灯的状态，变换的规则是：如果第i个灯左边的灯是亮着的，那么改变这个灯的状态（打开或者关掉），否则的话不变

思路：变换后第a[i]个灯的状态由变换前 a[i]和a[i+1]这两个灯的状态决定，可以得出a[i] = (a[i]+a[i-1])%2

那么，接下来就可以用矩阵的方法解决

|1 0 0 0 ... 1 1 | |an-1| = | a0 |

|1 1 0 0 ... 0 0 | | a0 | = | a1 |

|0 1 1 0 ... 0 0 | * | a1 | = | a2 |

|.. .. .. .. ... .. .. | | .... | = | ... |

|0 0 0 0 ... 1 1 | |an-2| = |an-1|

由于最后的结果是mod2的结果，因此我们可以把所有的*和+运算全部改成&和^

#include   
#include   
#include   
#include   
#include   
using namespace std;  
#define mod 1000007  
int n,len;  
struct node  
{  
    bool map[102][102];  
}unit,s;  
node Mul(node a,node b)  
{  
    node c;  
    int i,j,k;  
    for(i = 0; i < len; i ++)  
    for(j = 0; j < len; j ++)  
    {  
        c.map[i][j] = 0;  
        for(k = 0; k < len; k ++)  
        c.map[i][j] ^= a.map[i][k]&b.map[k][j];  
    }  
    return c;  
}  
void Matrix()  
{  
    while(n)  
    {  
        if(n&1) unit = Mul(unit,s);  
        n >




>= 1;  
        s = Mul(s,s);  
    }  
}  
int main()  
{  
    char a[102];  
    int b[102];  
    int i,j;  
    node sta;  
    memset(sta.map,0,sizeof(node));  
    for(i = 0; i < 101; i ++)  
    sta.map[i][i] = sta.map[i+1][i] = 1;  
    while(~scanf("%d%s",&n,a))  
    {  
        len = strlen(a);  
        for(i = 0; i < len; i ++)  
        b[i] = a[i] - '0';  
  
        memcpy(s.map,sta.map,sizeof(node));  
        memset(unit.map,0,sizeof(node));  
        s.map[0][len - 1] = 1;  
        for(i = 0; i < len; i ++)  
        unit.map[i][i] = 1;  
  
        Matrix();  
        for(i = 0; i < len; i ++)  
        {  
            bool sum = 0;  
            for(j = 0; j < len; j ++)  
            {  
                sum ^= unit.map[i][j]&b[j];  
            }  
            printf("%d",sum);  
        }  
        printf("\n");  
    }  
    return 0;  
}