解題區/解題區 - UVa

UVa 12045 - Fun with Strings

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Zibon just started his courses in Computer science. After having some lectures on programming courses he fell in love with strings. He started to play with strings and experiments on them. One day he started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b’s with ab and all the a’s with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the Nth string has the length X and Mth string has the length Y. He wondered what will be length of the Kth string. Can you help him?

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Five integers N, X, M, Y and K where (0 < N, M, X, Y, K < 109 and N ≠ M).

Output

For each test case produce one line of output giving either the number which is desired length (modulo 1000000007) or the string “Impossible”. You output Impossible if the given input is not possible.

Sample Input

1
2
3
2
3 16 5 42 6
5 1 6 10 9

Sample Output

1
2
68
Impossible

Solution

題目描述：

一開始由 a, b 構成的字串，每一次操作會將 a 換成 b, 將 b 換成 ab。
在第 N 次之後長度為 X、第 M 次之後長度為 Y，求第 K 次之後長度為何？

題目解法：

看到 a 換成 b, 將 b 換成 ab，其實只考量數量關係，很明顯是一個費式數列的關係。
因此，只要假設一開始有多少個 a，有多少個 b 在一開始的字串中，利用兩條方程式求解，之後再帶入費式數列的快速運算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Matrix {
    long long v[2][2];
    Matrix(long long a = 0) {
        memset(&v, 0, sizeof(v));
        for(int i = 0; i < 2; i++)
            v[i][i] = a;
    }
};
const long long mod = 1000000007LL;
Matrix multiply(Matrix x, Matrix y) {
    Matrix z;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++) {
                z.v[i][j] += x.v[i][k] * y.v[k][j] %mod;
                z.v[i][j] %= mod;
            }
    return z;
}
Matrix pow(Matrix x, long long y) {
    Matrix v(1);
    while(y) {
        if(y&1)
            v = multiply(v, x);
        y = y>>1, x = multiply(x, x); 
    }
    return v;
}
int main() {
    int testcase;
    long long N, X, M, Y, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lld %lld %lld %lld %lld", &N, &X, &M, &Y, &K);
        Matrix mm, na, nb, nc;
        mm.v[0][0] = mm.v[0][1] = mm.v[1][0] = 1;
        na = pow(mm, N);
        nb = pow(mm, M);
        nc = pow(mm, K);
        long long a1, b1, c1, a2, b2, c2;
        long long d, dx, dy;
        a1 = na.v[0][0], b1 = na.v[1][0], c1 = X;
        a2 = nb.v[0][0], b2 = nb.v[1][0], c2 = Y;
        d = a1 * b2 - a2 * b1;
        dx = X * b2 - Y * b1, dy = a1 * Y - a2 * X;
        if(d == 0 || dx%d || dy%d || dx/d < 0 || dy/d < 0)
            puts("Impossible");
        else {
            long long a = dx/d, b = dy/d;
            printf("%lld\n", (a * nc.v[0][0]%mod + b * nc.v[1][0]%mod)%mod);
        }
//		printf("%lld A + %lld B = %lld\n", na.v[0][0], na.v[1][0], X);
//		printf("%lld A + %lld B = %lld\n", nb.v[0][0], nb.v[1][0], Y);
//		printf("%lld A + %lld B = ????\n", nc.v[0][0], nc.v[1][0]);
    }
    return 0;
}