hdu 1005 Number Sequence

清疚 2021-10-13 01:59 269阅读 0赞

### hdu 1005 Number Sequence ###

*  题意
 *  题解
 *  源代码

[传送门][Link 1]

# 题意 #

现有有这样的一个递推式：
    f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
    给定A，B,n,求解f（n）

# 题解 #

由于n过大，如果直接线性O(n)求解可能会超时，所以需要从递推式中找到关系，
    易知f(n)需要对7进行取模，所以f(n)比较小，可知，f(n)在较小的范围就会循环，当
    连续的两个数在前面出现过，将会产生循环，所以这题需要找到循环节，f(n)<6,可以
    利用f(n-1)*10+f(n)作为一个标记，记录在序列出现的位置，当求解的时候，遇到时
    就退出循环，根据关系式直接求解f(n)即可

# 源代码 #

#include<iostream>
    using namespace std;
    const int maxn = 67;
    int main(){ 
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int a,b,n,c[maxn]={ 0,1,1},d[maxn];
        //c 代表需要求解的序列
        //d 标记f(n-1)*10+f(n)出现的位置，初始为0，代表为出现
        while (cin>>a>>b>>n&&(a+b+n))
        { 
            a%=7;
            b%=7;
            for(int i=0;i<maxn;++i)d[i]=0;
            d[11]=1;
            int i,j;
            for(i=3;i<=n;++i){ 
                c[i]=(c[i-1]*a+c[i-2]*b)%7;
                j = c[i-1]*10+c[i];
                if(d[j])break;//前面求解过，循环的地方
                d[j]=i-1;
            }
            if(n>=i)if(n>=i)n=(n-d[j])%(i-1-d[j])+d[j];
            // n - d[j]:n与循环开始的距离
            // i-1-d[j]:循环节的长度
            // +d[j]：加上循环初始的初始位置
            cout<<c[n]<<"\n";
        }
        
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1005