BZOJ2875 - [Noi2012]随机数生成器

2017/03/21

我好菜啊 _(:з」∠)_

小蒟蒻又开始写水题辣!

学到了一个 O(1) 快速乘的瞎写方法:

1
2
3
4
5
LL friend operator*(const LL &lhs, const LL &rhs) {
    LL ret = (lhs.x * rhs.x - LL((LD(lhs.x) / Mod * rhs.x + 1e-8)) * Mod);
    ret = ret < 0 ? ret + M : ret;
    return num{ ret };
}

这个写法的具体分析可见成都七中骆可强的《论程序底层优化的一些方法与技巧》

题目

给定递推公式:Xn+1 = (a Xn + c) mod m
求 Xn mod g

代码

很容易构造出来这个递推的转移矩阵:

 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef long double LD;

LL M, A, C, X0, N, G;

struct num {
    LL x;

    num friend operator+(const num &lhs, const num &rhs) {
        return num{ (lhs.x + rhs.x) % M };
    }

    num friend operator*(const num &lhs, const num &rhs) {
        LL ret = (lhs.x * rhs.x - LL((LD(lhs.x) / M * rhs.x + 1e-8)) * M);
        if(ret < 0) ret += M;
        return num{ ret };
    }
};

struct mat { num A[2][2]; };
// Trans = [ a 0 ] x [ X_i c ]
//         [ 1 1 ]

mat operator*(const mat &lhs, const mat &rhs) {
    mat ret;
    ret.A[0][0] = lhs.A[0][0] * rhs.A[0][0] + lhs.A[0][1] * rhs.A[1][0];
    ret.A[0][1] = lhs.A[0][0] * rhs.A[0][1] + lhs.A[0][1] * rhs.A[1][1];
    ret.A[1][0] = lhs.A[1][0] * rhs.A[0][0] + lhs.A[1][1] * rhs.A[1][0];
    ret.A[1][1] = lhs.A[1][0] * rhs.A[0][1] + lhs.A[1][1] * rhs.A[1][1];

    return ret;
}

mat operator^(const mat &lhs, LL k) {
    mat ret = lhs, base = lhs;
    for(--k;k;k>>=1,base=base*base) if(k & 1) ret = ret * base;
    return ret;
}

int main() {
    scanf("%lld %lld %lld %lld %lld %lld", &M, &A, &C, &X0, &N, &G);
    mat trans;
    trans.A[0][0] = num{A}; trans.A[0][1] = num{0};
    trans.A[1][0] = num{1}; trans.A[1][1] = num{1};

    trans = trans ^ N;

    LL ans = ((num{X0} * trans.A[0][0] + num{C} * trans.A[1][0]).x) % M % G;

    printf("%lld\n", ans);
}