很好的一题，也是我的队友xdp给我的题。
题意是根据字符串的变化规律，给出第n次和第m次变化的时候的长度，求出第k次变化时的长度。
开始的时候感觉这是难题，不过仔细想了一下，发现只需要高斯消元（其实在我这里只是一个简单的解二元一次方程组罢了。。囧）解出起始的时候a和b的个数，然后套上矩阵快速幂就可以得到第k项了。这题搞了整整一天，WA的地方居然是一个int没有改成LL。开始的时候，以为高斯消元做除法的过程中不会溢出，结果不知道为什么的，被我搞了好多数据之后，发现了一个会导致溢出的数据，改过来之后就过了！
代码如下：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 #define REP(i, n) for (int i = 0; i < (n); i++) 10 #define REP_1(i, n) for (int i = 1; i <= (n); i++) 11 12 typedef long long LL; 13 14 LL fab[60]; 15 void preFab() { 16 fab[0] = 0ll; 17 fab[1] = 1ll; 18 REP_1(i, 58) { 19 fab[i + 1] = fab[i] + fab[i - 1]; 20 // cout << i + 1 << ' ' << fab[i + 1] << endl; 21 } 22 } 23 24 LL mat[2][3]; 25 26 void swapRow() { 27 REP(i, 3) swap(mat[0][i], mat[1][i]); 28 } 29 30 bool test(int n, LL x, int m, LL y, int &a, int &b) { 31 if (n > 50 || m > 50) return false; 32 if (fab[n - 1] > x) return false; 33 if (fab[m - 1] > y) return false; 34 REP(i, 2) { 35 mat[0][i] = fab[n + i]; 36 mat[1][i] = fab[m + i]; 37 } 38 mat[0][2] = x; 39 mat[1][2] = y; 40 while (true) { 41 if (mat[0][0] > mat[1][0]) swapRow(); 42 if (mat[0][0]) { 43 LL tmp = mat[1][0] / mat[0][0]; 44 REP(i, 3) mat[1][i] -= tmp * mat[0][i]; 45 } else { 46 break; 47 } 48 } 49 swapRow(); 50 // REP(i, 2) { 51 // REP(j, 3) { 52 // cout << mat[i][j] << ' '; 53 // } 54 // cout << endl; 55 // } 56 57 LL ans[2]; 58 for (int i = 1; i >= 0; i--) { 59 if (mat[i][i]) { 60 if (mat[i][2] % mat[i][i]) return false; 61 ans[i] = mat[i][2] / mat[i][i]; 62 if (ans[i] < 0) return false; 63 for (int j = i - 1; j >= 0; j--) { 64 mat[j][2] -= mat[j][i] * ans[i]; 65 mat[j][i] = 0ll; 66 } 67 } else { 68 if (mat[i][2]) return false; 69 ans[i] = 0ll; 70 } 71 } 72 a = ans[0], b = ans[1]; 73 74 // REP(i, 2) { 75 // REP(j, 3) { 76 // cout << mat[i][j] << ' '; 77 // } 78 // cout << endl; 79 // } 80 // cout << a << "~~" << b << endl; 81 return true; 82 } 83 84 const int matSize = 2; 85 const LL mod = 1000000007; 86 struct Mat { 87 LL val[matSize][matSize]; 88 Mat(LL one = 0ll) { 89 REP(i, matSize) { 90 REP(j, matSize) { 91 val[i][j] = 0ll; 92 } 93 val[i][i] = one; 94 } 95 } 96 void print() { 97 REP(i, 2) { 98 REP(j, 2) { 99 cout << val[i][j] << ' ';100 }101 cout << endl;102 }103 cout << "~~~" << endl;104 }105 } ;106 107 Mat operator * (Mat &a, Mat &b) {108 Mat ret = Mat();109 REP(i, matSize) {110 REP(k, matSize) {111 REP(j, matSize) {112 ret.val[i][j] += a.val[i][k] * b.val[k][j] % mod;113 }114 }115 }116 return ret;117 }118 119 Mat operator ^ (Mat &a, int p) {120 Mat ret = Mat(1);121 Mat _a = a;122 while (p > 0) {123 if (p & 1) {124 ret = ret * _a;125 }126 _a = _a * _a;127 p >>= 1;128 }129 return ret;130 }131 132 LL work(int k, int a, int b) {133 Mat Base = Mat();134 Mat op = Mat();135 op.val[0][1] = op.val[1][0] = op.val[1][1] = 1ll;136 Base.val[0][0] = (LL) a;137 Base.val[0][1] = (LL) b;138 op = op ^ (k - 1);139 // op.print();140 Base = Base * op;141 // Base.print();142 return (Base.val[0][0] + Base.val[0][1]) % mod;143 }144 145 LL bruceForce(int k, int a, int b) {146 LL na = (LL) a, nb = (LL) b;147 REP(i, k - 1) {148 nb += na;149 na = nb - na;150 nb %= mod;151 }152 return (na + nb) % mod;153 }154 155 int main() {156 // freopen("in", "r", stdin);157 preFab();158 int n, m, k, na, nb, T;159 LL x, y;160 cin >> T;161 REP_1(cas, T) {162 cin >> n >> x >> m >> y >> k;163 printf("Case %d: ", cas);164 if (test(n, x, m, y, na, nb)) {165 // cout << na << ' ' << nb << endl;166 cout << work(k, na, nb) << endl;167 // cout << "~~~~~~~~ " << bruceForce(k, na, nb) << endl;168 } else {169 puts("Impossible");170 }171 }172 return 0;173 }
测试数据是：
Sample in:
4
1 1 2 1 107 277 8 448 139 842831057 38 321932817 1 （错在这个数据了）1 1003 7 16343 9000000
Sample out:
Case 1: 55
Case 2: 17Case 3: ImpossibleCase 4: 147991426
——written by Lyon