2019牛客暑期多校训练营（第五场） B generator 1（十进制矩阵快速幂）

深碍√TFBOYSˉ_ 2021-11-10 05:34 141阅读 0赞

## 题意：![20190802095758155.png][] ##

## 分析：十进制快速幂板子题。 ##

## 代码（模板）： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=1000005;
    LL mod;
    struct MAT{
        LL t[2][2];
        MAT operator * (const MAT&b)const{
            MAT res;
            memset(res.t,0,sizeof(res.t));
            for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++){
                res.t[i][j]=(res.t[i][j]+t[i][k]*b.t[k][j]%mod)%mod;
            }return res;
        }
    }a,b[N];
     
    char s[1000005];
    int main(){
        scanf("%lld%lld%lld%lld%s%lld",&a.t[0][0],&a.t[0][1],&b[0].t[1][1],&b[0].t[0][1],s+1,&mod);
        b[0].t[1][0]=1;
        int l=strlen(s+1);
        for(int i=l;i>=1;i--){
            b[l-i+1]=b[l-i];
            MAT tmp=b[l-i];
            for(int j=1;j<=9;j++){
                if(s[i]-'0'==j)a=a*b[l-i+1];
                b[l-i+1]=b[l-i+1]*tmp;
            }
        }
        printf("%lld\n",a.t[0][0]);
        return 0;
    }

[20190802095758155.png]: /images/20211109/ed79170483e5448fa97096379f6db1f9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019牛客暑期多校训练营（第四场）

Contest Info -------------------- [Contest Link][] <table> <thead> <tr> <t

淡淡的烟草味﹌/ 2023年06月04日 11:58/ 0 赞/ 92 阅读

相关 2019牛客暑期多校训练营（第一场）

Solutions -------------------- A：Equivalent Prefixes 题意：若$\\text\{RMQ(u,l,r)=RM

约定不等于承诺〃/ 2021年11月27日 04:44/ 0 赞/ 378 阅读

相关牛客多校第五场 B generator 1 矩阵快速幂

题意：给定$x\_0,x\_1,a,b,n,mod, x\_i=a\x\_\{i-1\}+b\x\_\{i-2\}$ ,求$x\_n % mod$ n最大有1e6位题

「爱情、让人受尽委屈。」/ 2021年11月11日 13:58/ 0 赞/ 166 阅读

相关 2019牛客暑期多校训练营（第五场） B generator 1（十进制矩阵快速幂）

题意：![20190802095758155.png][] 分析：十进制快速幂板子题。代码（模板）： include<bits/stdc++.h>

深碍√TFBOYSˉ_/ 2021年11月10日 05:34/ 0 赞/ 142 阅读

相关 2019牛客暑期多校训练营第六场

题目链接：[https://ac.nowcoder.com/acm/contest/886\question][https_ac.nowcoder.com_acm_contes

今天药忘吃喽~/ 2021年11月02日 13:38/ 0 赞/ 334 阅读

相关 2019牛客暑期多校训练营（第五场）- B generator 1 （齐次线性递推+矩阵快速幂）...

题目链接:https://ac.nowcoder.com/acm/contest/885/B 题意：已知齐次线性式xn=a\xn-1+b\xn-2，已知a，b，x0，x1，求

r囧r小猫/ 2021年10月30日 02:36/ 0 赞/ 143 阅读

相关 2019牛客暑期多校训练营（第五场）C - generator 2 (BSGS)

[题目链接][Link 1] 题意：给定\\(n,x\_0,a,b,p\\)，有递推式\\(x\_i = (a \\cdot x\_\{i-1\} +b)\\%p

我不是女神ヾ/ 2021年10月29日 07:48/ 0 赞/ 222 阅读

相关 2019牛客暑期多校训练营（第五场）

比赛链接：[https://ac.nowcoder.com/acm/contest/885\question][https_ac.nowcoder.com_acm_contes

左手的ㄟ右手/ 2021年10月26日 18:24/ 0 赞/ 342 阅读

相关 2019牛客暑期多校训练营（第一场）-B.Integration()

链接：https://ac.nowcoder.com/acm/contest/881/B 题意:给出n，和数组a\[n\]，求特定表达式取模后的值。思路：用到列项相消：!

旧城等待，/ 2021年10月01日 06:28/ 0 赞/ 287 阅读

相关 2019牛客暑期多校训练营（第一场）

<table> <thead> <tr> <th>Sloved</th> <th align="center">A</th> <th alig

绝地灬酷狼/ 2021年09月30日 02:02/ 0 赞/ 308 阅读