HDU2276_Kiki Little Kiki2_开关灯（构造矩阵）

一道好题，想不出为什么是矩阵，不过关键是我没有马上意识到mod2吧。

/*
*State: 2276    46MS    528K    2110 B    C++
*题目大意：
*        有n盏灯，0表示不亮，1表示亮，如果 i-th的灯的左边灯是亮的，那么下一秒钟，
*        i-th灯的状态要改变，0变成1，1变成0。问你在第t秒时，灯的状态时什么样的，输出来。
*解题思路：
*        00-->0,01-->1,10-->1,11-->0;
*        所以有a1 = (a1+an)%2,a2 = (a1+a2)%2,a3 = (a2+a3)%2,……an = (an+an-1)%2
*        能考虑到这里，构造矩阵就不难了。矩阵在这里被用来实现一个僵化的灯转换过程。
*解题感想：
*        很难一开始就想到用矩阵构造，主要是没有想到两两异或，然后变成两两相加模2.
*/

View Code

  1 #include <iostream>
  2 #include <cmath>
  3 #define maxn 101
  4 
  5 using namespace std;
  6 
  7 struct Mat
  8 {
  9     int m, n;
 10     int d[maxn][maxn];
 11     void init(int m, int n) 
 12     {
 13         this->m = m;
 14         this->n = n;
 15         memset(d, 0, sizeof(d));
 16     }
 17     void initE(int size)                              //生成单位阵
 18     {
 19         m = n = size;
 20         for(int i = 0; i < n; i ++)
 21         {
 22             for(int j = 0; j < n; j ++)
 23             {
 24                 d[i][j] = i==j;
 25             }
 26         }
 27     }
 28     Mat operator * (const Mat & mat) const
 29     {
 30         static Mat res;
 31         res.init(m, mat.n);
 32         for(int i = 0; i < res.m; i ++)
 33         {
 34             for(int k = 0; k < n; k ++)
 35             {
 36                 if(d[i][k]==0)    continue;
 37                 for(int j = 0; j < res.n; j ++)
 38                 {
 39                     res.d[i][j] += d[i][k] * mat.d[k][j];
 40                 }
 41             }
 42         }
 43         return res;
 44     }
 45     Mat mul_mod(const Mat & mat, int mod) const
 46     {
 47         static Mat res;
 48         res.init(m, mat.n);
 49         for(int i = 0; i < res.m; i ++)
 50         {
 51             for(int k = 0; k < n; k ++)
 52             {
 53                 if(d[i][k]==0)    continue;
 54                 for(int j = 0; j < res.n; j ++)
 55                 {
 56                     res.d[i][j]=(res.d[i][j]+d[i][k]*mat.d[k][j]) % mod;
 57                 }
 58             }
 59         }
 60         return res;
 61     }
 62     void pow_mod(int k, int mod)                      //this = this^k % mod;
 63     {
 64         static Mat a;
 65         a = *this;
 66         for(this->initE(n); k; k>>=1, a=a.mul_mod(a, mod))
 67             if(k&1)    *this=this->mul_mod(a, mod);
 68     }
 69 };
 70 
 71 int main(void)
 72 {
 73 #ifndef ONLINE_JUDGE
 74     freopen("in.txt", "r", stdin);
 75 #endif
 76     int t, mod = 2;
 77     char light[101];
 78     while(scanf("%d", &t) == 1)
 79     {
 80         scanf("%s", light);
 81         int len = strlen(light);
 82         Mat a, prea;
 83         a.init(len, len);
 84         prea.init(len, len);
 85         for(int i = 0; i < len; i++)
 86             prea.d[0][i] = light[i] - '0';
 87         for(int i = 0; i < len; i++)
 88         {
 89             a.d[i][i] = 1;
 90             if(i + 1 < len)
 91                 a.d[i][i + 1] = 1;
 92         }
 93         a.d[len - 1][0] = 1;
 94         a.pow_mod(t, mod);
 95         Mat ans = prea.mul_mod(a, mod);
 96         for(int i = 0; i < len; i++)
 97             printf("%d", ans.d[0][i]);
 98         printf("\n");
 99     }
100     return 0;
101 }