[NOI2012]随机数生成器【矩阵快速幂】

NOI2012 随机数生成器

题目描述

栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 \(m,a,c,X_0\)
，按照下面的公式生成出一系列随机数 \(\{X_n\}\)
：
\[X_{n+1}=(aX_n +c)\bmod m
\]

其中 \(mod\ m\)
表示前面的数除以 \(m\)
的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

栋栋知道这样产生的序列具有良好的随机性，不过心急的他仍然想尽快知道 \(X_n\)
是多少。由于栋栋需要的随机数是 \(0,1,\dots,g-1\)
之间的，他需要将 \(X_n\)
​ 除以 \(g\)
取余得到他想要的数，即 \(X_n \bmod g\)
，你只需要告诉栋栋他想要的数 \(X_n \bmod g\)
是多少就可以了。

输入格式

一行 \(6\)
个用空格分割的整数 \(m,a,c,X_0,n\)
和 \(g\)
，其中 \(a,c,X_0\)
是非负整数， \(m,n,g\)
是正整数。

输出格式

输出一个数，即 \(X_n \bmod g\)
。

输入输出样例

输入

输出

2

说明/提示

计算得 \(X_n=X_5=8\)
，故 \((X_n \bmod g) = (8 \bmod 3) = 2\)
。

对于 \(100\%\)
的数据， \(n,m,a,c,X_0\leq 10^{18}\)
， \(1\leq g\leq 10^8\)
， \(n,m\geq 1\)
， \(a,c,X_0\geq 0\)
。

题意

给出了一个迷惑式子，让你算出来式子的第 \(n\)
项，然后 \(mod\ g\)
的结果

分析

看到这样一个个的递推式子，一个个用 \(for\)
循环来推肯定不行，所以很容易就会想到要用到矩阵快速幂来求。那么我们现在的主要任务就是构造矩阵来进行乘法运算。
首先看到题目中给出的式子：
\[X_{n+1}=(aX_n+c)\ mod\ m
\]
取模运算可以暂且先不看，因为对结果没什么影响，在矩阵乘法的时候进行取模就行了。所以转化成如下式子：
\[X_{n+1}=aX_n+c
\]

那么我们就可以根据这个式子来构造矩阵。由矩阵的乘法运算为结果矩阵的 \(i\)
行 \(j\)
列为前边矩阵一个的第 \(i\)
行乘以另一个的第 \(j\)
列，所以我们可以得出如下的矩阵递推式子：
\[\left[
\begin{matrix}
X_{n-1}\\
c
\end{matrix}
\right]\times \left[
\begin{matrix}
a & 1\\
0 & 1
\end{matrix}
\right] = \left[
\begin{matrix}
X_{n}\\
c
\end{matrix}
\right]
\]

这里用 \(X_{n-1}\)
这一列分别乘以右边矩阵的第一第二行，得到结果的矩阵，那么我们就可以根据这个递推式子来进行矩阵快速幂。
这里乘法的运算过程如下：
\[X_{n-1}\times a+c\times 1 = X_n
\]
\[X_{n-1}\times 0+c\times 1 = c
\]
由此得到结果矩阵

这里的矩阵做乘法的时候需要用到龟速乘，不然会爆 \(long\ long\)

代码

#include
using namespace std;
#define int long long
struct Node{//矩阵结构体
    int a[5][5];
};
int m,a,c,x0,g,n;
int ksj(int a,int b){//龟速乘
    int ans = 0;
    while(b){
        if(b & 1)ans = (ans + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return ans;
}
Node Mul(Node a,Node b,int c){//矩阵乘法，记得取模
     Node ans;
     memset(ans.a,0,sizeof(ans.a));
     for(int i=1;i<=2;++i){
         for(int j=1;j<=2;++j){
             for(int k=1;k>= 1;
    }
}
signed main(){
    Node bas;
    scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
    ans.a[1][1] = x0;//初始化矩阵
    ans.a[2][1] = c;
    bas.a[1][1] = a;
    bas.a[1][2] = 1;
    bas.a[2][1] = 0;
    bas.a[2][2] = 1;
    qpow(ans,bas,n);
    printf("%lld\n",ans.a[1][1] % g);//得答案
}