题解 P5678 【[GZOI2017]河神】

· · 题解

为了方便，我们记序列 b 下标从 1 开始，并翻转，这样可以化为标准的线性递推式。

考虑用矩阵快速幂来解决，此处我们更改矩阵乘法的定义：将原本的乘法改为按位与，原本的加法改为按位或。

那么就能得到：

\begin{bmatrix} a_{n-1} & a_{n-2} &\dots &a_{n-k}\end{bmatrix} \times \begin{bmatrix} b_1 &+\infty &0 & \dots & 0 \\ b_{2} & 0 & +\infty & \dots & 0 \\b_3 & 0 & 0 & \dots & 0 \\ \dots & \dots & \dots & \dots & \dots \\ b_{k-1} & 0 & 0 & \dots & +\infty\\ b_k & 0 & 0 & \dots & 0\end{bmatrix} =\begin{bmatrix} a_n & a_{n-1} &\dots &a_{n-k+1}\end{bmatrix}

这里的 +\infty 指的是二进制中每一位都是 1 的数。

然后直接做就行了。

（水题解的屑）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<bitset>
#define N 100003
#define reg register
#define ull unsigned long long
#define inf 0xffffffffffffffffull
using namespace std;

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

struct matrix{
    ull a[101][101];
    int siz;

    inline matrix(int siz=0):siz(siz){ memset(a,0,sizeof(a)); }
    inline matrix operator * (const matrix& b) const{
        matrix res = matrix(siz);
        for(reg int i=0;i!=siz;++i)
        for(reg int j=0;j!=siz;++j)
        for(reg int k=0;k!=siz;++k)
            res.a[i][j] |= a[i][k]&b.a[k][j];
        return res;    
    }
};

inline matrix power(matrix a,int t){
    matrix res = matrix(a.siz);
    for(reg int i=0;i!=a.siz;++i) res.a[i][i] = inf;
    while(t){
        if(t&1) res = res*a;
        a = a*a;
        t >>= 1;
    }
    return res;
}

int n,k;
ull a[N],f[103];
matrix A;

int main(){
    ull ans = 0;
    scanf("%d%d",&n,&k);
    for(reg int i=0;i<k;++i) scanf("%llu",&a[i]);
    for(reg int i=1;i<=k;++i) scanf("%llu",&f[i]);
    if(n<=k){
        printf("%llu",a[n]);
        return 0;
    }
    reverse(f+1,f+k+1);
    for(reg int i=0;i!=k;++i) A.a[i][0] = f[i+1];
    for(reg int i=1;i!=k;++i) A.a[i-1][i] = inf;
    A.siz = k;
    A = power(A,n-k+1);
    for(reg int i=0;i<k;++i)
        ans |= a[k-i-1]&A.a[i][0];
    printf("%llu",ans);
    return 0;
}