LuoguP2044「NOI2012」题解

发表于

我回来啦!

Description

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

$$X_{n+1} = (aX_n + c) \bmod m$$

从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。

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

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

Samples

Input #1

1
11 8 7 1 5 3

Output #1

1
2

Solution

题目中给出了一个递推式,那么考虑通过矩阵快速幂来求.

首先我们设$\rm {A}$表示初始矩阵,$\rm {B}$表示转移矩阵, 那么最后的答案矩阵应该是$\rm {A \times B^n}$.

那么根据矩阵快速幂的套路,我们设出矩阵$\rm {A,B}$的每一个元素,然后根据题目中的递推式列出式子.

具体推导过程如下:
lEaUSJ.md.png

我的博客渲染好像对于大括号和矩阵出了点问题,暂且先放个图片吧qaq

容易发现,根据方程组得出的两组解都是成立的,那么我们随便选取一种作为初始/转移矩阵即可啦

Code

这里的代码选取了上面推导过程中的第一个根.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/* Headers */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <stack>
#include <map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define RevEdge(x) x^1
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE], *is = ibuf, *its = ibuf;
    char obuf[BUFSIZE], *os = obuf, *ot = obuf + BUFSIZE;
    inline char getch() {
        if(is == its)
            its = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
        return (is == its) ? EOF : *is++;
    }
    inline int getint() {
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-') {neg = 1;ch = getch();}
        while(isdigit(ch)) {
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg ? -res : res;
    }
    inline void flush(){
        fwrite(obuf, 1, os - obuf, stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot) flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--) putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
#define int long long
#define ull unsigned long long
struct Matrix {
    int arr[3][3];
    Matrix () {memset(arr, 0, sizeof arr);}
} ans, base;
int m, a, c, _X, n, g;
/* functions */
inline int quick_multi(int a, int b, int p) {
    int k = (long double) a / p * b;
    int res = (ull)a * b - (ull)k * p;
    return (res + p) % p;
}
inline Matrix mul(Matrix a, Matrix b, int mod) {
    Matrix res;
    FOR(i, 1, 2, 1) {
        FOR(j, 1, 2, 1)
            FOR(k, 1, 2, 1) {
                res.arr[i][j] += quick_multi(a.arr[i][k], b.arr[k][j], mod);
                res.arr[i][j] %= mod;
                if(res.arr[i][j] < 0) res.arr[i][j] += mod;
            }
    } return res;
}
inline Matrix Matrix_power(int b, int p) {
    Matrix res; res.arr[1][1] = res.arr[2][2] = 1;
    while(b) {
        if(b & 1) res = mul(res, base, p);
        b >>= 1; base = mul(base, base, p);
    } return res;
}
signed main(void) {
    //FILE_IN("data.in");
    scanf("%lld %lld %lld %lld %lld %lld", &m, &a, &c, &_X, &n, &g);
    a %= m; c %= m; _X %= m;
    if(n == 0) return printf("%lld\n", _X) & 0;
    ans.arr[1][1] = _X, ans.arr[1][2] = 1;
    base.arr[1][1] = a, base.arr[2][1] = c, base.arr[2][2] = 1;
    base = Matrix_power(n, m); ans = mul(ans, base, m);
    printf("%lld\n", ans.arr[1][1] % g);
    return 0;
}

THE END