lightOJ 1052 String Growth(矩阵快速幂，找规律)

超、凢脫俗 2022-06-09 08:49 168阅读 0赞

## String Growth ##

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 length X and Mth string has length Y. He wondered what will be length of the Kth string. Can you help him?

**Input**  
Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case begins with five integers N, X, M, Y, K. (0 < N, M, X, Y, K < 109 and N ≠ M).

**Output**  
For each case print one line containing the case number and L which is the desired length (mod 1000000007) or the string “Impossible” if it’s not possible.

**Sample Input**  
2  
3 16 5 42 6  
5 1 6 10 9  
**Sample Output**  
Case 1: 68  
Case 2: Impossible

**题意**：有一种字符串只由a和b组成，字符串每次变化，a都会变成b，b会变成ab，比如aba→babb→abbabab，现在告诉你第n次变化的字符串长度是x，第m次变化的字符串长度是y，问你第k次变化时字符串的长度。初始字符串未知。

**思路**：我们先随便列几项看看  
a→b→ab→bab→abbab→bababbab→abbabbababbab→……  
每一串a，b的个数如下  
![这里写图片描述][SouthEast]

显而易见，a和b都呈斐波那契数列，总和自然也是斐波那契数列。虽然我们不知道字符串的初始状态，但是我们可以根据题目给的两个状态去反推。  
已知a和b的关系可以表示成以下矩阵递推式  
![这里写图片描述][SouthEast 1]  
根据题目给的两个状态，可以列出方程组![这里写图片描述][SouthEast 2]  
然后我们利用矩阵快速幂就可以找到a\[n\],b\[n\],a\[m\],b\[m\]分别对应多少倍的a\[-1\]+多少倍的b\[-1\]。（我们知道a，b的位置应该从1开始，但是这里我们往前额外算两位，这样可以判断出第一位和第二位不满足条件的情况）然后就变成了二元一次方程组，求解出a\[-1\]和b\[-1\]后，就可以再用一次矩阵快速幂求出任意位置的字符串长度。  
然后接下来就是考虑Impossible的情况。  
1，我们可以先找一个使所有位置字符串长度最短的情况，那就是第一个字符串是a的情况，也就是我们上面举的那个例子，同一位置下其它情况的字符串的长度都会比该情况要长。所以说如果第k个位置的字符串长度比这个最短的情况还要短，那就是Impossible。  
2，1中的字符串长度最短的情况，在不超过题目数据范围的情况下所能达到的位置是最远的。因为题目给你的数据范围只到1e9，所以说任何情况下位置都不能超过第一种情况的最远位置。如果不太好理解的话我举个例子：  
![这里写图片描述][SouthEast 3]  
3，如果出现了m>n而x>y的情况，很明显是Impossible，因为由题意可知不能出现后者比前者小的情况。  
4，解方程组的时候，如果解出来a\[-1\]和b\[-1\]不是整数，或者小于0，直接Impossible。  
5，在解出a\[-1\]和b\[-1\]的值之前，如果使用矩阵快速幂的过程中取了模，那也说明数据不正确，Impossible。

#include <cstdio> 
    #include <cstring> 
    #include <cmath> 
    #include <iostream> 
    #include <algorithm> 
    using namespace std;
    #define LL long long 
    const int mod = 1e9 + 7;
    struct matrix {
        LL f[2][2];
    };
    LL flag, mark, dp[100];
    void init()
    {
        LL i, j, k;
        dp[0] = 0;
        dp[1] = 1;
        for (i = 2;; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
            if (dp[i] >= 1e9)break;
        }
        mark = i;
    }
    matrix mul(matrix a, matrix b)
    {
        LL i, j, k;
        matrix c;
        memset(c.f, 0, sizeof(c.f));
        for (i = 0; i<2; i++)
        {
            for (j = 0; j<2; j++)
            {
                for (k = 0; k<2; k++)
                {
                    c.f[i][j] = c.f[i][j] + a.f[i][k] * b.f[k][j];
                    if (c.f[i][j] >= mod || c.f[i][j] <= -mod)
                    {
                        flag = 1;
                        c.f[i][j] %= mod;
                    }
                }
            }
        }
        return c;
    }
    matrix pow_mod(matrix a, LL b)
    {
        matrix s;
        s.f[0][0] = s.f[1][1] = 1;
        s.f[0][1] = s.f[1][0] = 0;
        while (b)
        {
            if (b & 1)s = mul(s, a);
            a = mul(a, a);
            b = b >> 1;
        }
        return s;
    }
    int main()
    {
        init();
    
        LL T, tt = 0;
        cin >> T;
        while (T--)
        {
            LL n, m, x, y, k, i, j;
            flag = 0;
            cin >> n >> x >> m >> y >> k;
            if (n>m)
            {
                swap(n, m);
                swap(x, y);
            }
            cout << "Case " << ++tt << ": ";
            if (y<x || m >= mark || x<dp[n] || y<dp[m]) { cout << "Impossible" << endl; continue; }
            matrix e, g, gg;
            e.f[0][0] = 0; e.f[1][0] = e.f[0][1] = e.f[1][1] = 1;
            g = pow_mod(e, n - 1);
            gg = pow_mod(e, m - 1);
            LL a, b, c, d, p, q;
            a = g.f[0][0] + g.f[1][0];
            b = g.f[0][1] + g.f[1][1];
            c = gg.f[0][0] + gg.f[1][0];
            d = gg.f[0][1] + gg.f[1][1];
            if (flag || (c*x - a*y) % (b*c - a*d) || (d*x - b*y) % (a*d - b*c)) { cout << "Impossible" << endl; continue; }
            p = (d*x - b*y) / (a*d - b*c);
            q = (c*x - a*y) / (b*c - a*d);
            if (p<0 || q<0) { cout << "Impossible" << endl; continue; }
            g = pow_mod(e, k - 1);
            cout << (p*(g.f[0][0] + g.f[1][0]) + q*(g.f[0][1] + g.f[1][1])) % mod << endl;
        }
        return 0;
    }

[SouthEast]: /images/20220609/8f91adb47a424ef093a05e0cc0de9e3d.png
[SouthEast 1]: /images/20220609/b7d6a7245e044ba5a6e519cc49d4e844.png
[SouthEast 2]: /images/20220609/9282b602aff94545b2169dc4f518eb08.png
[SouthEast 3]: /images/20220609/86ab943886bf474b880f72816229fe1e.png