还是矩阵快速幂的题，将异或的操作转换成矩阵乘法。1y！
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 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