LightOJ 1052 String Growth（数学递推+矩阵快速幂求斐波拉契数列）

╰+攻爆jí腚メ 2022-06-09 09:13 202阅读 0赞

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 **M**th 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.

<table style="color:rgb(0,0,0); font-family:Arial; font-size:14px"> 
 <tbody> 
  <tr> 
   <td> <h1 style="margin:0px; padding:0px; color:green"><a style="color:rgb(255,153,0)" rel="nofollow"></a><span style="font-size:18px">Sample Input</span></h1> </td> 
   <td> <h1 style="margin:0px; padding:0px; color:green"><a style="color:rgb(255,153,0)" rel="nofollow"></a><span style="font-size:18px">Output for Sample Input</span></h1> </td> 
  </tr> 
  <tr> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:18px">2</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:18px">3 16 5 42 6</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:18px">5 1 6 10 9</span></p> </td> 
   <td> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:18px">Case 1: 68</span></p> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="font-size:18px">Case 2: Impossible</span></p> </td> 
  </tr> 
 </tbody> 
</table>

题解：

题意：

有一个串只有a和b组成，长度未知

有一种操作，每次将串中的a变成b，b变成ab

给你第d1次的长度x1，d2次的长度为x2,让你求第k次的长度

思路：

设一开始第一次a有x个，b有y个，一共x+y个，发现下一次为a有y个，b有x+y个，然后它的下一次a有x+y个，b有x+2\*y个。。以此类推可以发现数列是由两个斐波拉契数列系数和未知数组成的式子，那么我们知道次数d1和d2那么我们就知道他x和y的系数是多少（假设次数为d1，那么x，y的系数就分别是就是斐波拉契数列的第d1项和d1+1项），由于这个k的值可以达到1e9，很大，普通的o（n）算法肯定会炸，那么这里就一定要用矩阵快速幂来算

今天向老刘请教了下矩阵快速幂，就是可以说只要可以用公式表达的数列就可以用矩阵快速幂算出第i项，像斐波拉契数列Fn=Fn-1 + Fn-2

那么矩阵就是个2x2的：

1 1 换行1 0 该矩阵的n-2次方乘以矩阵F2 换行 F1，那么最后的矩阵乘上F2就是Fn的值（这部分矩阵快速幂不太好讲解可以另外学一下，第一排的是Fn-1和Fn-2的系数，下一排根据式子情况推出），然后我们知道两个关于x，y的式子就可以像解方程一样解出x和y，这里我用了欧几里得求最小公倍数。。好像可以不用的，当解出的x不为整数，或者y不为整数，或者任意一个小于0那么就impossible，否则就再用矩阵快速幂求出第k项

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    const ll mod=1000000007;
    ll b[5][5];
    ll t[5][5];
    void cheng(ll x[][5],ll y[][5])//矩阵x成矩阵y，最后结果放在x中
    {
        memset(t,0,sizeof(t));
        int i,j,k;
        for(i=0;i<2;i++)
        {
            for(j=0;j<2;j++)
            {
                for(k=0;k<2;k++)
                {
                    t[i][j]=(t[i][j]+x[i][k]*y[k][j]%mod)%mod;
                }
            }
        }
        for(i=0;i<2;i++)
        {
            for(j=0;j<2;j++)
            {
                x[i][j]=t[i][j];
            }
        }
    }
    ll squre(ll d)//矩阵快速幂
    {
        if(d==1||d==2)//特判1,2
           return (ll)1;
        int i,j,k,l;
        ll t1,t2,c=d-2;
        b[0][0]=b[0][1]=b[1][0]=1;//初始化矩阵
        b[1][1]=0;
        ll answer[5][5];
        answer[0][0]=answer[1][1]=1;
        answer[0][1]=answer[1][0]=0;//矩阵快速幂初始化对角线为1，其余为0
        while(c>0)
        {
            if(c%2)
            {
                cheng(answer,b);
            }
            cheng(b,b);
            c/=2;
        }
        return (answer[0][0]+answer[0][1])%mod;
    }
    ll ojld(ll x,ll y)//欧几里得求最大公约数
    {
        ll r=x%y;
        while(r!=0)
        {
            x=y;
            y=r;
            r=x%y;
        }
        return y;
    }
    int main()
    {
        int i,j,test,q,tag;
        ll d1,x1,d2,x2,k,t1,t2,c1,c2,x,y,com,add1,add2,tot;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            tag=1;
            scanf("%lld%lld%lld%lld%lld",&d1,&x1,&d2,&x2,&k);
            if(d1>d2)
            {
                swap(d1,d2);
                swap(x1,x2);
            }
            t1=squre(d1);
            c1=squre(d1+1);
            t2=squre(d2);
            c2=squre(d2+1);
            com=t1*t2/ojld(t1,t2);//求最小公倍数
            add1=com/t1;
            add2=com/t2;
            if((x2*add2-x1*add1)%(c2*add2-c1*add1))
                tag=0;
            else
            {
                y=(x2*add2-x1*add1)/(c2*add2-c1*add1);
                x=(x1-c1*y)/t1;
                if((x1-c1*y)%t1||x<0||y<0)
                    tag=0;
                else
                {
                    tot=(x*squre(k)%mod+y*squre(k+1)%mod)%mod;
                }
            }
            printf("Case %d: ",q);
            if(!tag)
                printf("Impossible\n");
            else
                printf("%lld\n",tot);
        }
        return 0;
    }