洛谷P5678 [GZOI2017]河神 题解

题目链接：P5678 [GZOI2017]河神

题意：

cxy 从河神给的选择中，获得了一道当年挂掉的代数题的灵感。

但现在他希望你来帮忙解答，因为他自己忙着去搜妹纸资源去了。

给出数列 $\{a_n\}$ 和 $\{b_n\}$ 以及 $\{A_n\}$ 的递推关系，试求出数列 $\{A_n\}$ 第 $N$ 项。

递推关系为：

$$A_n=\begin{cases}a_n & 0 \le n < K \\[8pt] \bigoplus (A_{n-K+t} \otimes b_t) & n \ge K \end{cases}$$

其中，$\otimes$ 表示与操作，$\oplus$ 表示或操作。

输入格式：

第一行两个正整数 $N$ 和 $K$ 。

第二行 $K$ 个空格隔开的非负整数，表示 $\{a_n\}$。

第三行 $K$ 个空格隔开的非负整数，表示 $\{b_n\}$。

输出格式：

一行，一个整数，表示$\{A_n\}$。

数据范围：

$0 \le a_i,b_i \le 2^{63} - 1,~ n \le 10^9,~ k \le 100$

考虑推广矩阵乘法使其仍满足结合律。

我们可以把 加法 变成 或运算，乘法 变成 与运算。简单证明一下：

$((AB)C)_{i,j}$ 的第 $d$ 位为 $1$ 当且仅当存在至少一对 $x,y$ 使得 $A_{i, x}, B_{x, y}, C_{y, j}$ 第 $d$ 位均为 $1$ 。

$(A(BC))_{i,j}$ 的第 $d$ 位为 $1$ 当且仅当存在至少一对 $x,y$ 使得 $A_{i, x}, B_{x, y}, C_{y, j}$ 第 $d$ 位均为 $1$ 。$\square$

则初始矩阵为：

$$A = \left[\begin{array}{llll} a_{k} & a_{k-1} & \cdots & a_{0} \end{array}\right]$$

转移矩阵：（ $e$ 为单位元，取 $2^{63} - 1$ 即可 ）

$$M = \left[\begin{array}{ccccc} b_1 & e &&& \\b_2 && e & \\\vdots &&& \ddots \\b_{k-1} &&&& e \\b_k &&&& \end{array}\right]$$

只要算下 $A \times M^{n - k + 1}$ 就好啦~

时间复杂度 $\mathcal{O}(k^3 \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

mat mul(mat A, mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p));
    for(int k = 0; k < m; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < p; j++)
                C[i][j] |= A[i][k] & B[k][j];
    return C;
}
mat qpow(mat A, int b)
{
    int n = max(A.size(), A[0].size());
    mat ans(n, vector<int>(n));
    for(int i = 0; i < n; i++) ans[i][i] = INT64_MAX;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,K; cin >> n >> K;
    mat M(K, vector<int>(K)), A(1, vector<int>(K));
    for(int i = 0; i < K; i++) cin >> A[0][K - i - 1];
    for(int i = 0; i < K; i++) cin >> M[K - i - 1][0];
    if(n < K) return cout << A[0][n] << '\n', 0;
    for(int i = 1; i < K; i++) M[i - 1][i] = INT64_MAX;
    mat res = mul(A, qpow(M, n - K + 1)); cout << res[0][0] << '\n';
    return 0;
}