「Luogu 5110」块速递推

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：Luogu 5110

给定一个数列 $a$ 满足递推式：

求这个数列第 $n$ 项 $a_n\bmod (10^9+7)$ 的值，一共有 $T$ 组询问。为了减少你的输出量，你只需要输出所有询问答案的异或和。

数据范围：$0\le n<2^{64}$，$1\le T\le 5\times 10^7$

Solution

先考虑朴素的做法，我们可以直接用矩阵乘法和矩阵快速幂在 $O(2^3T\log n)$ 的时间内求解。矩乘的式子如下：

接下来我们考虑如何优化。由于 $T$ 的范围很大，我们需要保证每次询问的复杂度为 $O(1)$。首先有一个非常显然的性质 $a^b\equiv a^{b\bmod \varphi(p)}\pmod p$，因此我们把式子转化为：

虽然有这样一个转化，但是我的复杂度瓶颈却在矩阵快速幂的 $O(\log n)$ 上，考虑如何优化掉这个 $\log$：由于询问很多，我们需要在常数时间内回答，考虑预处理矩阵的幂。

我们令矩阵 $A=\left[\begin{matrix}233 & 666\\ 1 & 0\end{matrix}\right]$，我们预处理出两部分矩阵的幂。

首先我们令 $k=\left\lceil\sqrt{10^9+6}\right\rceil$（$10^9+6$ 也就是 $n$ 的最大值）。此处注意一定要上取整，不然预处理的幂可能不充分。

  1. 预处理 $A^1,A^2,A^3,\cdots,A^k$，将矩阵 $A^i$ 记为 $X(i)$。
  2. 预处理 $A^k,A^{2k},A^{2k},\cdots,A^{k^2}$，将矩阵 $A^{ik}$ 记为 $Y(i)$。

很显然以上两部分的复杂度均为 $O(k)$。

我们把询问 $m$（此处的 $m$ 为 $(n-1)\bmod \varphi(10^9+7)$）拆成 $m=ak+b$，其中 $0\le b<k$。转化为数学语言为 $a=\left\lfloor\frac{m}{k}\right\rfloor,b=m\bmod k$，于是 $A^m$ 转化为 $(A^k)^a\times A^b$，根据我们上面预处理的部分，我们可以发现，$(A^k)^a$ 和 $A^b$ 都是可以直接查表得到的。所以 $A^m=(A^k)^a\times A^b=X(b)\times Y(a)$。

这样我们的询问复杂度就降低为 $O(1)$（其实应该是矩阵乘法复杂度 $O(2^3)$），加上常数优化即可通过本题！

吐槽：此题卡常！出题人毒瘤！

时间复杂度：$O(T+\sqrt{10^9+6})$（其中 $\sqrt{10^9+6}$ 约为 $32000$ 左右）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <cstdio>
#include <cstring>

const int N=32000,mod=1e9+7;
struct Matrix {
    int mat[2][2];
    Matrix operator * (const Matrix &b) const {
        Matrix ans;
        ans.mat[0][0]=(1LL*mat[0][0]*b.mat[0][0]+1LL*mat[0][1]*b.mat[1][0])%mod;
        ans.mat[0][1]=(1LL*mat[0][0]*b.mat[0][1]+1LL*mat[0][1]*b.mat[1][1])%mod;
        ans.mat[1][0]=(1LL*mat[1][0]*b.mat[0][0]+1LL*mat[1][1]*b.mat[1][0])%mod;
        ans.mat[1][1]=(1LL*mat[1][0]*b.mat[0][1]+1LL*mat[1][1]*b.mat[1][1])%mod;
        return ans;
    }
} p1[N+5],p2[N+5];
unsigned long long SA,SB,SC;

unsigned long long rand() {
    SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
    unsigned long long t=SA;
    SA=SB,SB=SC,SC^=t^SA;
    return SC;
}
int main() {
    Matrix s;
    s.mat[0][0]=233,s.mat[0][1]=666,s.mat[1][0]=1,s.mat[1][1]=0;
    p1[0].mat[0][0]=p1[0].mat[1][1]=1;
    for(int i=1;i<=N;++i) p1[i]=p1[i-1]*s;
    p2[0].mat[0][0]=p2[0].mat[1][1]=1,s=p1[N];
    for(int i=1;i<=N;++i) p2[i]=p2[i-1]*s;
    int T;
    scanf("%d%llu%llu%llu",&T,&SA,&SB,&SC);
    int ans=0;
    for(int i=1;i<=T;++i) {
        int n=(rand()-1)%(mod-1);
        ans^=(p2[n/N]*p1[n%N]).mat[0][0];
    }
    printf("%d\n",ans);
    return 0;
}
0%