电脑是一个很神奇的东西。小小的CPU里装着很多很多的计算。有些数是连用人脑也需要费一些时间。但是电脑依旧可以在短时间内算出来。但是电脑的算法和人的算法是远远不一样的。电脑的算法只有零和一直说也就是二进制，而人的算法则是由零到九，是十进制。



在昨晚从一写到五百一十二然后每个数都转换为二进制，一开始在写的时候觉得真是太难了，那么多数怎么写呀？但是写了写却发现二进制的排列是有顺序的。可以在数与数之间找到一些规律。当然逢二进一就不用多说了。比如说十进制的奇数转化为二进制的时候，尾数肯定是一，十进制的偶数转化为二进制的时候，尾数肯定是零。还有尾数是由00   01   10   11的顺序4个一轮回持续循环的，再说每一竖排从后向前看，是01 01 01 （2的0次方）然后是0011 0011 0011（2的1次方） 、00001111 00001111 00001111（2的2次幂）~~~~也是呈现2的n次方增长数间隔的。



当然接触到二进制的时候就肯定会接触到十进制转化为二进制和二进制转化为十进制。在二进制转化为十进制的加法方法中，要总结了很多条规律。比如说2的n次方就是1后面有n个零、用大数求小数再持续性求和找节点等等。



这样的二进制让我感受到和十进制不一样的数字感。觉得研究计算机的人确实很厉害，创造二进制的人也是很有头脑。

题意：

给了递推式， ,已知 和，求。

 

思路：

听了出题人的讲解，才知道矩阵快速幂还能这样的优化！

我们保留这四个最基本的矩阵：，，，

那么怎么进行十进制优化呢？

举个例子：

比如：，这个用十进制优化怎么求？

我们可以用保留的矩阵来拼出23的低位的3

那么20怎么算出来呢？

这时候，我们就先拼出个10来：我们先让。

这样我们的实际上就是原来的，然后我们在用来更新，，。这样就能通过这些来得到幂次是10~100的了。(真神奇）

 

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll mod;
char s[maxn];
struct Matrix
{
    ll a[2][2];
    Matrix(){
        memset(a,0,sizeof(a));
    }
    friend Matrix operator * (Matrix a, Matrix b)
    {
        Matrix tmp;
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    (tmp.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod)%=mod;
                }
            }
        }
        return tmp;
    }
};
int main()
{
    ll x,y,a,b;
    scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
    scanf("%s",s);
    scanf("%lld",&mod);
    int len=strlen(s);
    Matrix tmp[4],ans;
    tmp[0].a[0][0]=a;
    tmp[0].a[0][1]=b;
    tmp[0].a[1][0]=1;
    tmp[0].a[1][1]=0;
    tmp[1]=tmp[0]*tmp[0];
    tmp[2]=tmp[1]*tmp[1];
    tmp[3]=tmp[2]*tmp[2];
    ans.a[0][0]=ans.a[1][1]=1;
    for(int i=len-1;i>=0;i--){
        int x=s[i]-'0';
        for(int j=0;j<4;j++){
            if(x>>j&1){
                ans=ans*tmp[j];
            }
        }
        tmp[0]=tmp[1]*tmp[3];
        tmp[1]=tmp[0]*tmp[0];
        tmp[2]=tmp[1]*tmp[1];
        tmp[3]=tmp[2]*tmp[2];
    }
    printf("%lld\n",(ans.a[1][0]*y%mod+ans.a[1][1]*x%mod)%mod);
    return 0;
}


 

冯洛伊曼计算机结构特点：冯洛伊曼结构模型采用存储程序方式
计算机有运算器、控制器、存储器、输入设备及输出设备五大基本部件组成
存储器用于存放指令和数据；运算器完成算术运算和逻辑运算；操作人员通过输入设备和输出设备使用计算机
计算机内部以二进制形式表示指令和数据；每条指令由操作码和地址码组成；操作码指出操作类型；地址码指出操作数的地址；由一串指令组成程序。
硬件：中央处理器：数据通路(指令执行过程中所流经的部件，包括各类运算部件，最重要的是ALU算数逻辑部件)、控制器(用来对指令的译码，生成相应的控制信号，以控制数据通路进行特定操作)
存储器：内存(主存和高速缓冲存储器)、外存(辅助存储器和海量后备存储器)
外部设备：输入设备、输出设备、I/O控制器(控制外部设备的控制逻辑)
总线：数据信息传输的通路，CPU、主存、I/O控制器通过总线互连
软件：系统软件操作系统
语言处理程序
数据库管理系统(DBMS)实用程序——磁盘碎片整理程序等
应用软件：专门为某一程序所编写的各类程序
计算机系统的层次结构
最终用户：使用应用程序完成特定任务的计算机用户
系统管理员：指利用操作系统等软件提供的功能对系统进行配置、维护和管理，以建立高效合理的系统环境供计算机用户使用的操作人员
应用程序员：指使用高级编程语言编制应用软件的程序员
系统程序员：指设计和开发系统软件的程序员
程序由多条指令组成
指令的执行过程：根据PC取指令到IR
指令译码并送出控制信号
取操作数
执行指令
写回结果
PC更新：为了能自动执行程序中的指令，CPU必须能够自动得到下一条指令的地址并送到PC；所以取出指令送到IR后稳定后，PC自动更新。定长指令字系统：每条指令的长度都一样PC=PC+指令长度(相同值)
不定长指令字系统：每条指令的长度不一样PC=PC+指令长度(不同值)
指令周期：从一条指令的启动到下一条指令的启动之间的间隔时间
机器周期：是指令执行中每一步操作所需的时间。一般以CPU中完成一个运算操作所需的时间作为机器周期的基本时间，机器周期也称CPU周期。
时钟周期：指计算机的主频周期，也称T周期或T状态
吞吐率(带宽)：表示在单位时间内所完成的工作量。
响应时间(执行时间或等待时间)：是指从作业提交开始到作业完成所需要的时间。
CPU时间：指CPU用于程序执行的时间，包括用户CPU时间和系统CPU时间。
用户CPU时间计算需用到的指标：时钟周期：用于对控制信号定时的同步信号即为CPU的时钟信号，其宽度为一个时钟周期
时钟频率：CPU的主频
CPI：表示执行一条指令所需的时钟周期数。CPU执行时间=程序所含时钟周期数÷时钟频率
=程序所含时钟周期数×时钟周期
程序总时钟周期数=程序所含指令条数×CPI
MIPS:平均每秒钟执行多少百万条指令。
MFLOPS：表示每秒所执行的浮点运算有多少百万次，是基于所完成的操作次数而不是指令数来衡量。
基准程序是一个测试程序集，由一组程序组成。是专门用来进行性能评价的一组程序。
SPEC测试程序集是应用最广泛，也是最全面的性能评测基准程序集。

在阅读本文之前，建议没有基础的读者先阅读下主存的基本组成结构：
五分钟理解主存储器的基本组成结构
存储单元的字地址：
我们来看张图：
在上面的图中，每一个小矩形代表一个存储单元，大矩形表示主存中的存储体。
通常都是以8位二进制为一个存储单元，也就是一个字节。然后在我们的计算机中，不管是笔记本还是台式机，总会听到CPU一次处理数据的能力是32位还是64位，其实，这个32位或者64位就是用来表示字长。字长用来表示字的长度。而字就是由字节构成。
在上图中，一个存储单元为1个字节，这4个字节又构成一个字，每个字有字地址，在上图中表示出来了。关于字地址的表示方式，也有两种，这两种表示方法的区别，我后面也会用一篇文章来解释清楚。
那么，上图的字长为多少呢？
我们来分析下，4个字节构成一个字，一个字节等于8个比特，所以总共就是32位了。现在我们的计算机，都是64位了，很少有32位的计算机出现了。
举例：
在学习到主存储体的章节时，这三道题我们经常会看到，经常会有小伙伴很迷惑，不知道怎么分析，我们来看下下面三道题：
1.设地址线为24根，按字节寻址，有多少存储字？
2.如果存储容量不变，若字长为16位，按字寻址有多少存储字？
3.如果存储容量还不变，若字长为32，按字寻址有多少存储字？
 我们先分析下第一个问题。
这里假如地址线有24根，由于地址也是用2进制表示的，那么每根地址线就有0或者1两位，地址可以表示为从00000..00000(24位)—11111...11111(24位)。一共就有2^24位，也就是2^24个地址。转化之后就是16MB的地址。这些地址表示存储单元的位置，所以存储单元的个数也就是16MB。
那么，16MB怎么计算的呢？
2^24Byte(字节)=16777216Byte
16777216Byte/1024=16384KByte
 16384KByte/1024 = 16MByte
而且，1Byte=8Bit，那么16MByte = 128Mbit。
第一个问题的意思就是，一个字等于8比特，也就是一个字节。一个存储单元可以存放一个8位二进制数，这个二进制数就是一个存储字。其实，就是问有多少个存储单元。经过计算，就是16MB个。
 我们先分析下第二个问题。
在上面第一个例子中，一个存储单元中有8位，那么16MB个存储单元中，可以存放16MB×8位。就是存储单元的容量，简称存储容量。
那么，第二个问题中，存储容量不变，就是一样有16MB×8的空间。字长为16位，我们按字寻址，有多少个存储字？
如果是按字寻址，我们知道字长16位，那么总容量除以字长就是存储字的个数：
（16MB*8）/ 16 = 8M
那么第三个问题也是一样的，只是把字长换成了32
（16MB*8）/ 32 = 4M
CSDN链接：
CSDN-专业IT技术社区-登录​blog.csdn.net