题解 P5678

· · 题解

Solution

给定了递推式，要快速求递推式的值，显然想到矩阵快速幂

我们将矩阵快速幂中原本的加法定义为"|"运算（即按位或），将乘法定义为"&"运算（即按位与），根据题意，写出转移式：

\left[ \begin {matrix} A_i & A_{i-1} & A_{i-2} & \dots & A_{k}\end {matrix} \right] = \left[ \begin {matrix} A_{i-1} & A_{i-2} & A_{i-3} \dots & A_{k-1}\end {matrix} \right] \times \left[ \begin {matrix} b_k & maxx & 0 & \cdots & 0 \\ b_{k-1} & 0 & maxx & \cdots & 0 \\ b_{k-2} & 0 & 0 &\cdots & 0 \\ \vdots & \vdots&\vdots &\ddots &\vdots \\ b_{1} & 0 & 0 &\cdots &0 \end {matrix} \right]

其中maxx = 2^{63}-1，同时为方便起见，b数组下标统一+1

转移矩阵Mat1（就是柿子里的最后一个矩阵）简单来说就是第1列第j行为b_{k-j+1}，第i列i+1行为maxx，其余的都为0

根据题意，初始矩阵为

Mat0 = \left[ \begin{matrix}a_k & a_{k-1} & a_{k-2} & \cdots & a_1 \end{matrix}\right]

同样为方便起见，a数组下标统一+1

所以最终答案就是Ans矩阵的Ans_{1, 1}，其中Ans矩阵为：

Ans = Mat0 \times Mat1^{n-k+1}

注意题目中A数组是从0开始编号的，所以是Mat1^{n-k+1}而不是Mat1^{n-k}

还有就是当n \leq k的时候要特判

时间复杂度O(k^3 \log n)

Code

#include <bits/stdc++.h>

#define N (int) 105
#define ll long long

using namespace std;
ll input () {
    ll x = 0, f = 0;
    char c = getchar ();
    while (c < '0' || c > '9') f = c == '-', c = getchar ();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar ();
    return f ? - x : x;
}

const ll maxx = (1ull<<63)-1;

int n, k;
ll a[N], b[N];

struct Matrix { // 矩阵
    int n, m;
    ll a[N][N];
    friend Matrix operator * (const Matrix & x, const Matrix & y) { // 定义矩阵乘法
        Matrix ret;
        ret.n = x.n, ret.m = y.m;
        for (int i = 1; i <= x.n; i ++) {
            for (int j = 1; j <= y.m; j ++) {
                for (int k = 1; k <= x.m; k ++) {
                    ret.a[i][j] |= x.a[i][k] & y.a[k][j];
                }
            }
        }
        return ret;
    }
    Matrix () {
        n = m = 0;
        memset (a, 0, sizeof (a));
    }
} mat0, mat1;

Matrix ksm (Matrix x, int y) { // 矩阵快速幂
    Matrix ret = x;
    y --;
    while (y) {
        if (y & 1) ret = ret * x;
        x = x * x;
        y >>= 1;
    }
    return ret;
}

int main () {
    n = input (), k = input ();
    for (int i = 1; i <= k; i ++) a[i] = input ();
    for (int i = 1; i <= k; i ++) b[i] = input ();

    if (n <= k) { // 特判
        printf ("%lld\n", a[n]);
        return 0;
    }

    mat1.n = mat1.m = k; // 转移矩阵
    for (int i = 1; i <= k; i ++)
        mat1.a[i][1] = b[k-i+1];
    for (int i = 1; i < k; i ++)
        mat1.a[i][i+1] = maxx;
    mat0.n = 1, mat0.m = k; // 初始矩阵
    for (int i = 1; i <= k; i ++)
        mat0.a[1][i] = a[k-i+1];

    Matrix ans = mat0 * ksm (mat1, n-k+1);

    printf ("%lld\n", ans.a[1][1]);

    return 0;
}

Conclusion

1 加速递推式——矩阵快速幂

2 注意一些细节（如下标从0开始之类的）