hdu 2276 Kiki & Little Kiki 2

http://acm.hdu.edu.cn/showproblem.php?pid=2276
　　还是矩阵快速幂的题，将异或的操作转换成矩阵乘法。1y！
代码如下：
View Code
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cassert>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 const int maxSize = 100;
  9 const int initMod = 1E9 + 7;
 10 int curSize = maxSize;
 11 int curMod = initMod;
 12 
 13 struct Matrix {
 14     int val[maxSize][maxSize];
 15 
 16     Matrix(bool ONE = false) {
 17         for (int i = 0; i < curSize; i++) {
 18             for (int j = 0; j < curSize; j++) {
 19                 val[i][j] = 0;
 20             }
 21             if (ONE) val[i][i] = 1;
 22         }
 23     }
 24 
 25     void print(int _l = curSize, int _w = curSize) {
 26         for (int i = 0; i < _l; i++) {
 27             for (int j = 0; j < _w; j++) {
 28                 if (j) putchar(' ');
 29                 printf("%d", val[i][j]);
 30             }
 31             puts("");
 32         }
 33         puts("~~");
 34     }
 35 };
 36 
 37 Matrix operator * (Matrix &_a, Matrix &_b) {
 38     Matrix ret = Matrix();
 39 
 40     for (int i = 0; i < curSize; i++) {
 41         for (int k = 0; k < curSize; k++) {
 42             if (_a.val[i][k]) {
 43                 for (int j = 0; j < curSize; j++) {
 44                     ret.val[i][j] += _a.val[i][k] * _b.val[k][j];
 45                     ret.val[i][j] %= curMod;
 46                 }
 47             }
 48         }
 49     }
 50 
 51     return ret;
 52 }
 53 
 54 Matrix operator ^ (Matrix &_a, int _p) {
 55     Matrix __a = _a, ret = Matrix(true);
 56 
 57     while (_p) {
 58         if (_p & 1) {
 59             ret = ret * __a;
 60         }
 61         __a = __a * __a;
 62         _p >>= 1;
 63     }
 64 
 65     return ret;
 66 }
 67 
 68 char *deal(int n) {
 69     char *buf = new char[101];
 70     int p = 0;
 71 
 72     scanf("%s", buf);
 73     curSize = strlen(buf);
 74 
 75     Matrix Base = Matrix(), op = Matrix(true);
 76 
 77     while (buf[p]) {
 78         Base.val[0][p] = buf[p] - '0';
 79         p++;
 80     }
 81     for (int i = 1; i < curSize; i++) {
 82         op.val[i - 1][i] = 1;
 83     }
 84     op.val[curSize - 1][0] = 1;
 85 //    op.print();
 86 
 87     op = op ^ n;
 88     Base = Base * op;
 89 
 90     p = 0;
 91     while (buf[p]) {
 92         buf[p] = Base.val[0][p] + '0';
 93         p++;
 94     }
 95 
 96     return buf;
 97 }
 98 
 99 int main() {
100     int n;
101 
102     curMod = 2;
103     while (~scanf("%d", &n)) {
104         printf("%s\n", deal(n));
105     }
106 
107     return 0;
108 }
——written by Lyon