洛谷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;
}