博主的 BiBi 时间

傻逼弱智脑残二百五三千六题！（失去理智）

我 \(TM\) 把加速矩阵写成了 \(2*3\) 调了半天交了十几次！我真的 \(fo\) 了。

Solution

其实就是矩阵加速 \(+\) 整除分块。

我们考虑去掉 \(\lfloor\frac{p}{n}\rfloor\) 这一项，其实这就变成了矩阵加速的模板题。我们用整除分块可以将这个快速幂分成几段来乘，每一段的 \(\lfloor\frac{p}{n}\rfloor\) 不一样就行了。

我们算一下时间复杂度：整除分块的次数是 \(\sqrt{n}\) 级别，那么每次大约是 \(\sqrt{n}\) 的长度，那么就是

（虽然这个估计很粗略跑不满还是感觉自己算错了怎么办）

Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;

ll a, b, c, d, p, N;
struct Matrix {
    ll s[4][4];
    Matrix() {memset(s, 0, sizeof s);}
    Matrix operator * (const Matrix t) {
        Matrix r;
        for(int i = 1; i <= 3; ++ i)
            for(int j = 1; j <= 3; ++ j)
                if(s[i][j])
                    for(int k = 1; k <= 3; ++ k)
                        r.s[i][k] = (r.s[i][k] + s[i][j] * t.s[j][k]) % mod;
        return r;
    }
} per, A;

Matrix qkpow(int y) {
    Matrix r;
    for(int i = 1; i <= 3; ++ i) r.s[i][i] = 1;
    while(y) {
        if(y & 1) r = r * per;
        per = per * per; y >>= 1;
    }
    return r;
}

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < ‘0‘ || s > ‘9‘) if(s == ‘-‘) f = -1;
    while(s >= ‘0‘ && s <= ‘9‘) {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

void init(const int x) {
	for(int i = 1; i <= 3; ++ i)
		for(int j = 1; j <= 3; ++ j)
			per.s[i][j] = 0;
    per.s[3][2] = per.s[2][1] = per.s[3][3] = 1;
    per.s[1][2] = c; per.s[2][2] = d;
    A.s[1][3] = x;
}

int main() {
    ll lim;
    for(int T = read(); T; -- T) {
        a = read(), b = read(), c = read(), d = read(), p = read(), N = read();
        if(N == 1) {printf("%lld\n", a); continue;}
		lim = min(N, p);
        A.s[1][1] = a, A.s[1][2] = b;
        for(int l = 3, r; l <= lim; l = r + 1) {
            r = min(N, p / (p / l));
            init(p / l);
            per = qkpow(r - l + 1);
			A = A * per;
        }
        lim = max(2ll, p);
        if(lim < N) init(0), per = qkpow(N - lim), A = A * per;
        printf("%lld\n", A.s[1][2]);
    }
    return 0;
}
/*
F1 F2 something

0  C  0
1  D  0
0  1  1

2
3 3 2 1 3 5
3 2 2 2 1 4

*/

HDU - 6395 Sequence

原文：https://www.cnblogs.com/AWhiteWall/p/12933672.html