M_sea

洛谷2044 [NOI2012]随机数生成器
题目描述栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congrue...
扫描右侧二维码阅读全文
04
2018/08

洛谷2044 [NOI2012]随机数生成器

题目描述

栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数m,a,c,X[0],按照下面的公式生成出一系列随机数{Xn}:

                       X[n+1]=(aX[n]+c) mod m

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

用这种方法生成的序列具有随机序列的性质,因此这种方法被广泛地使用,包括常用的C++和Pascal的产生随机数的库函数使用的也是这种方法。

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

传送门

算法

显然,$x_{n+1}$只和$x_{n}$有关。

考虑矩阵加速。题目有:

$$x_{n+1}=x_{n}\times a+c$$

但是这个$c$不好搞,所以考虑再加一个常数$1$。

那么应该是这样:

$$x_{n+1}=x_{n}\times a+1\times c$$

$$1=x_{n}\times 0+1\times 1$$

所以构造出这样的矩阵:

a 0
c 1

接下来基本上是板子了。

但是,本题中$m$最大有$10^{18}$,所以矩乘时直接乘会爆long long!

所以要把Mul中的乘换为龟速乘。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int MOD; 

struct Matrix {
    int m[110][110];
};

inline int iMul(int a,int b){
    int rt=0;
    while (b){
        if (b&1) rt=(rt+a)%MOD;
        a=(a+a)%MOD;
        b>>=1;
    }
    return rt;
}

inline Matrix Mul(Matrix a,Matrix b,int n) {
    Matrix c;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            c.m[i][j]=0;
            for (re int k=1;k<=n;k++)
                c.m[i][j]=(c.m[i][j]+iMul(a.m[i][k],b.m[k][j]))%MOD;
        }
    return c;
}

Matrix FastPow(Matrix a,int k,int n) {
    Matrix rt;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            if (i==j) rt.m[i][j]=1;
            else rt.m[i][j]=0;
        }
    while (k) {
        if (k&1) rt=Mul(rt,a,n);
        a=Mul(a,a,n);
        k>>=1;
    }
    return rt;
}

Matrix A,B;

mainint main() {
    MOD=read();
    int a=read()%MOD,c=read()%MOD,x0=read()%MOD,n=read(),g=read();
    
    A.m[1][1]=x0,A.m[1][2]=1,A.m[2][1]=A.m[2][2]=0;
    B.m[1][1]=a,B.m[1][2]=0,B.m[2][1]=c,B.m[2][2]=1;
    
    A=Mul(A,FastPow(B,n,2),2);
    printf("%lld\n",A.m[1][1]%g);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 57 PM

发表评论