JZOJsenior3366.【NOI2012】随机数生成器

problem

Description

栋栋最近迷上了随机算法，而随机数生成是随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数 m, a, c, X0，按照下面的公式生成出一系列随机数：

Xn+1=(aXn+c) mod m

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

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

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

Input

输入中包含 6 个用空格分割的整数m, a, c, X0, n和g，其中a, c, X0是非负整数，m, n, g是正整数。

Output

输出一个数，即Xn mod g

Sample Input

11 8 7 1 5 3

Sample Output

2

Data Constraint

Hint

Xn的前几项依次是:

k 0 1 2 3 4 5

Xk 1 4 6 0 7 8

因此答案为X5 mod g = 8 mod 3 = 2

---

analysis

哇，NOI2012的原题耶~然而懂得矩阵乘法套路的我十分钟码完
（所以说这道题应该是NOI的第一题……如果提高组的第一题也有这么水就好了=v=）

这题虽说O（n）的暴力也能拿到50分，但在考场上有多少OIers会满足于区区50分呢？
正解：矩阵乘法get√

---

构造矩阵式

首先我们可以很明显地推出一个东西：

(An)×(ac)=(a⋅An+c)

明显地，这个矩阵式对解题没有任何意义，why？
既然是矩阵的幂，那么中间那个转移矩阵必须是n×n的，否则乘不起来

那么，从初始矩阵出发，我们尝试把转移矩阵变成n×n的：

把(An)写成(An,p)，那么——

(An,p)×(a,0c,1)=(a⋅An+c,p)

（注意，这步是十分灵活的，给原矩阵添一些无用的元素可能是解决问题的关键）
所以——

(A0,p)×(a,0c,1)n=(An,p)

（反正我取的p是1，其实p取什么值都无所谓）

---

所以，这道题就变得十分简单啦，直接套矩乘模板快速幂，then AC

（另，你想想两个10^18的long long乘起来会不会炸掉？
答案是肯定的，WA85，解决方法是把所有long long的相乘换成快速乘即可
快速乘姿势）

---

快速乘code

long long mul(long long x,long long y)
{
    long long ans=0;
    while (y)
    {
        if (y&1)ans=(ans+x)%m;
        x=2*x%m;
        y/=2;
    }
    return ans;
}

其实快速乘和快速幂没什么区别……变了两个字母而已（但它不会爆long long就对了）

code

#include<cstdio>

using namespace std;

long long m,a,c,x0,n,g;

struct matrix
{
    long long m[2][2];
};

matrix I=
{
    1,0,
    0,1
};

long long mul(long long x,long long y)
{
    long long ans=0;
    while (y)
    {
        if (y&1)ans=(ans+x)%m;
        x=2*x%m;
        y/=2;
    }
    return ans;
}

matrix operator *(matrix a,matrix b)
{
    matrix c;
    for (int i=0;i<=1;i++)
    {
        for (int j=0;j<=1;j++)
        {
            c.m[i][j]=0;
            for (int k=0;k<=1;k++)(c.m[i][j]+=mul(a.m[i][k],b.m[k][j]))%=m;
        }
    }
    return c;
}

matrix power(matrix a,long long k)
{
    matrix ans=I,p=a;
    while (k)
    {
        if (k&1)ans=ans*p;
        p=p*p;
        k/=2;
    }
    return ans;
}


int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
    matrix A=
    {
        a,0,
        c,1
    };
    matrix answer=power(A,n);
    long long k=(mul(x0,answer.m[0][0])+answer.m[1][0])%m;
    printf("%lld",k%g);
    return 0;
}