题解 P5678 【[GZOI2017]河神】

· · 题解

本题是对 矩阵概念理解 的考察

前置讲解

我们先来看一下矩阵的定义式

\sum_{k = 1}^m A_{i, k} \times B_{k, j}

然后我们发现根据题意 发现这道题目实质上是

将 求和 变成 或 |

将 乘法 变成 与 &

故只要将矩阵乘法的板子的运算符号改一下就阔以了。 即

\bigoplus_{k = 1}^m A_{i, k} \otimes B_{k, j}

解题思路

得到上面柿子之后我们对转移矩阵进行构造，因为每次转移需要用到 k 个值

所以状态矩阵大小 1 \times k, 转移矩阵大小 k \times k

模拟题意

易构造出矩阵

状态矩阵

A_n & A_{n - 1} & \cdots & A_{n - k + 1}\\ \end{bmatrix}

转移矩阵

b_{n - 1} & INF &\cdots &\cdots & 0 \\ b_{n-2} &0 & INF &\cdots & 0 \\ \vdots &0 &0 & INF & \cdots \\ b_{n - k + 1} &\cdots & \cdots & \cdots&INF\\ b_{n - k } &\cdots &\cdots & \cdots & 0 \end{bmatrix}

其中 INF & a （a < 2^{63}）的值都为 a

INF 取 (1 << 63) - 1 就行了

下面就是正常的矩阵快速幂的过程，这里不再赘述。

code

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x <<endl;
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define INF ((1ull << 63) - 1) 
using namespace std;
template<typename Tp> void Cmax(Tp &x, Tp y) { x = max(x, y); }
template<typename Tp> void Csum(Tp &x, Tp y) { x = x + y; }
template<typename Tp>
void read(Tp &x){
    x = 0; int f = 1;
    char ch = getchar();
    while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); }
    while(isdigit(ch)){ x = x * 10 + ch - 48; ch = getchar(); }
    x = x * f;
}
typedef unsigned long long ULL;
typedef double doub;
const int N = 130;
int n, k;
ULL f[N], C[N][N];
void mul(){
    ULL ff[N];
    memset(ff, 0, sizeof ff);
    rep(i, 0, k - 1)
        rep(j, 0, k - 1)
            ff[i] |= f[j] & C[j][i]; // 实质上改的 只有这里 
    memcpy(f, ff, sizeof f);
}
void mulself(){
    ULL ff[N][N];
    memset(ff, 0, sizeof ff);
    rep(i, 0, k - 1)
        rep(j, 0, k - 1)
            rep(t, 0, k - 1)
                ff[i][j] |= C[i][t] & C[t][j]; // 改的只 有这里 
    memcpy(C, ff, sizeof C);
}
signed main(){
    read(n); read(k);
    for(int i = k - 1; i >= 0; --i)
        read(f[i]);
    for(int i = k - 1; i >= 0; --i)
        read(C[i][0]);
    rep(i, 0, k - 1)
        C[i][i + 1] = INF; 
    if(k >= n){
        printf("%llu\n", f[k - n]);
        return 0;
    }
    n = n - k + 1;
    while(n){
        if(n & 1) 
            mul();
        n >>= 1;
        mulself();
    }
    printf("%llu\n", f[0]);
    return 0;
}