首页 / 算法 / 蓝桥杯 算法提高 递推求值

蓝桥杯 算法提高 递推求值

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯 算法提高 递推求值，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1782字，纯文字阅读大概需要3分钟。

内容图文

题目如下：

问题描述
　　已知递推公式：
　　F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,
　　F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.
　　初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
　　输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以99999999的余数。
输入格式
　　输入第一行包含一个整数n。
输出格式
　　输出两行，第一行为F(n, 1)除以99999999的余数，第二行为F(n, 2)除以99999999的余数。
样例输入
4
样例输出
14
21
数据规模和约定
　　1<=n<=10^18。
-----分割线-----
　　在拿到此题后，就知道这题应该是矩阵快速幂，但是因为以前只做过简单的斐波那契数列的矩阵快速幂，所以完全不知道这题该怎么构造矩阵，后来翻了百度上的很多博客。简单来说，就是找到一个矩阵A满足：x(n-1)*A=x(n)。当然，此题不同于一般的“x(n)、x(n-1)”。要做如下构造：
　　[f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),f(n-3,1),f(n-3,2),5,3]*A=[f(n,1),f(n,2),f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),5,3]
　　即把前三项当做x(n-1),后一项以及前三项的后两项当做x(n),易知矩阵为8阶矩阵，具体见代码：
#include<stdio.h>
#define max 99999999
#define ll long long int
typedef struct Matrix
{
    ll m[8][8];
}mat;
mat multi(mat x,mat y,int a,int b,int c)
{
    int i,j,k;
    mat z;
    for(i=0;i<8;i++)
        for(j=0;j<8;j++)
            z.m[i][j]=0;
    for(i=0;i<a;i++)
        for(j=0;j<c;j++)
            for(k=0;k<b;k++)
                z.m[i][j]=(z.m[i][j]+(x.m[i][k]*y.m[k][j])%max)%max;
    return z;
}
int main()
{
    ll n,v1,v2,i;
    mat A={ 0,1,1,0,0,0,0,0,
            1,0,0,1,0,0,0,0,
            0,0,0,0,1,0,0,0,
            0,0,0,0,0,1,0,0,
            2,3,0,0,0,0,0,0,
            0,2,0,0,0,0,0,0,
            1,0,0,0,0,0,1,0,
            0,1,0,0,0,0,0,1
                            };
    mat E={ 1,0,0,0,0,0,0,0,
            0,1,0,0,0,0,0,0,
            0,0,1,0,0,0,0,0,
            0,0,0,1,0,0,0,0,
            0,0,0,0,1,0,0,0,
            0,0,0,0,0,1,0,0,
            0,0,0,0,0,0,1,0,
            0,0,0,0,0,0,0,1,
                            };
    ll s[8]={6,5,1,4,2,3,5,3};
    scanf("%I64d",&n);
    if(n==1)
        printf("2\n3");
    if(n==2)
        printf("1\n4");
    if(n==3)
        printf("6\n5");
    if(n>=4)
    {
        n-=3;
        while(n)
        {
            if(n%2)
                E=multi(E,A,8,8,8);
            n/=2;
            A=multi(A,A,8,8,8);
        }
        v1=0;
        v2=0;
        for(i=0;i<8;i++)
        {
            v1=(v1+(s[i]*E.m[i][0])%max)%max;
            v2=(v2+(s[i]*E.m[i][1])%max)%max;
        }
        printf("%I64d\n%I64d",v1,v2);
    }
    return0;
}

 

原文：https://www.cnblogs.com/search-the-universe/p/holiday-4.html

内容总结

以上是互联网集市为您收集整理的蓝桥杯 算法提高 递推求值全部内容，希望文章能够帮你解决蓝桥杯 算法提高 递推求值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1208384.html

来源：【匿名】