P4838 P哥破解密码 题解

· · 个人记录

P4838 P哥破解密码 题解

题目传送门

题意简述

$1 \le m \le 10, 1 \le n \le 10^9$。 ## 前置知识 - 矩阵乘向量 - 矩阵快速幂 ## 解法 ### 70pts 设 $f_{i,x}$ 为长度为 $i$，末尾有正好 $x$ 个 $0$ 的方案数。 $f_{i,0} = f_{i-1,0}+f_{i-1,1}+f_{i-1,2} f_{i,1} = f_{i-1,0} f_{i,2} = f_{i-1,1}

其中 f_{0,0} = 1, f_{0,1} = 0, f_{0,2} = 0。

答案为 f_{n,0}+f_{n,1}+f_{n,2}。

时间复杂度 O(nt+m)。

100pts

因为 n 达到了 10^9，用矩阵优化。

设：

A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} B = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}

计算 A^n B 即可。使用矩阵快速幂。

时间复杂度 O(m t^3 \log n)。空间复杂度 O(t^2)。

100pts(2)

注意到这题有多测，我们可以使用时间复杂度更低的矩阵乘向量进行优化。（矩阵乘法 O(t^3)，矩阵乘向量 O(t^2)）

预处理 A^1,A^2,A^4,A^8 \cdots，每次取 O(\log n) 个矩阵乘在向量上。

时间复杂度 O(t^3 \log n + m t^2 \log n)。空间复杂度 O(t^2 \log n)。

虽然时间复杂度变小了，空间复杂度变大了，但是为什么在洛谷的时间和空间都没有任何变化。

代码

#include <bits/stdc++.h>
#define memset0(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long LL;

const int MOD = 19260817;

struct Matrix {
    LL M[4][4];
    void clear() {
        memset0(M);
    }
    void reset() {
        clear();
        for (int i = 1; i <= 3; i++)
            M[i][i] = 1;
    }
    Matrix friend operator*(const Matrix &A, const Matrix &B) {
        Matrix C; C.clear();
        for (int i = 1; i <= 3; i++)
            for (int k = 1; k <= 3; k++)
                for (int j = 1; j <= 3; j++)
                    (C.M[i][j] += A.M[i][k] * B.M[k][j] % MOD) %= MOD;
        return C;
    }
};
struct Vector {
    LL M[4];
    void clear() {
        memset0(M);
    }
};
Vector operator*(const Matrix &A, const Vector &B) {
    Vector C; C.clear();
    for (int i = 1; i <= 3; i++)
        for (int k = 1; k <= 3; k++)
            (C.M[i] += A.M[i][k] * B.M[k] % MOD) %= MOD;
    return C;
}

Matrix A; Vector B;
Matrix Mat[31];

int main() {
    A.clear();
    A.M[1][1] = 1; A.M[1][2] = 1; A.M[1][3] = 1;
    A.M[2][1] = 1;
                   A.M[3][2] = 1;

    Mat[0] = A;
    for (int i = 1; i <= 30; i++)
        Mat[i] = Mat[i-1] * Mat[i-1];

    int t; scanf("%d", &t); while (t--) {
        LL n; scanf("%lld", &n);
        Vector B; B.clear(); B.M[1] = 1;
        int cnt = 0;
        while (n) {
            if (n & 1)
                B = Mat[cnt] * B;
            n >>= 1;
            cnt++;
        }
        printf("%lld\n", (B.M[1] + B.M[2] + B.M[3]) % MOD);
    }
    return 0;
}