洛谷P4838 P哥破解密码 题解

题目链接：P4838 P哥破解密码

题意：

定义一个串合法，当且仅当串只由 $\tt{A}$ 和 $\tt{B}$ 构成，且没有连续的 $3$ 个 $\tt{A}$ 。

P哥知道，密码就是长度为 $N$ 的合法字符串数量对$19260817$取模的结果。

但是P哥不会算，所以他只能把 $N$ 告诉你，让你来算

至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P哥也不记得了

然而他忘记字符串长度 $N$ 应该是多少了，于是他准备试 $M$ 组数据。

输入格式：

第一行给出一个整数 $M$ 表示询问次数

接下来M行每行给出一个正整数 $N$ ，表示该组询问中字符串的长度

输出格式：

对于每一次询问输出一行一个整数表示答案

数据范围：

$N\leq 10^9,~M\leq 10$

设 $f_{i,j}$ 表示长度为 $i$ 的字符串，有长为 $j(j = 0,1,2)$ 的后缀全为 $\tt{A}$ ，则

$$f_{i,0} = f_{i - 1,0} + f_{i - 1,1} + f_{i - 1,2} \\ f_{i,1} = f_{i - 1,0} \\ f_{i,2} = f_{i - 1,1}$$

边界：$f_{0,0} = 1, f_{0,1} = f_{0,2} = 0$ 。

注意到 $N$ 很大，考虑使用矩阵快速幂优化，如下

$$\left[\begin{array}{lll} f_{0,2} & f_{0,1} & f_{0,0} \end{array}\right] \times\left[\begin{array}{lll} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{array}\right]^n=\left[\begin{array}{lll} f_{n, 2} & f_{n, 1} & f_{n, 0} \end{array}\right]$$

时间复杂度 $\mathcal{O}(m\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
const int mod = 19260817;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
#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++)
                add(C[i][j], A[i][k] * B[k][j] % mod);
    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] = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
mat A(1, vector<int>(3)), B(3, vector<int>(3));
void clear()
{
    // nothing
}
void work()
{
    int n, sum = 0; cin >> n;
    mat res(1, vector<int>(3)); res = mul(A, qpow(B,n));
    for(int i = 0; i < 3; i++) add(sum, res[0][i]);
    cout << sum << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    A[0][2] = 1; B[1][0] = B[2][1] = B[0][2] = B[1][2] = B[2][2] = 1;
    // for(int i = 0; i < 3; i++)
    //     for(int j = 0; j < 3; j++) cout << B[i][j] << " \n"[j == 2];
    int _Q; cin >> _Q; while(_Q--) work();
    return 0;
}