P哥破解密码 题解【递推】【矩阵加速递推】

点击量：146

    1e9的类似dp的东西以后都要想矩阵加速了噢。

目录

题目背景

P哥是一个经常丢密码条的男孩子。

 

在ION 8102赛场上,P哥又弄丢了密码条,笔试满分的他当然知道这可是要扣5分作为惩罚的,于是他开始破解ION Xunil系统的密码。

 

题目描述

定义一个串合法，当且仅当串只由A和B构成，且没有连续的3个A。P哥知道，密码就是长度为N的合法字符串数量对19260817取模的结果。但是P哥不会算，所以他只能把N告诉你，让你来算

 

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

 

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

 

输入输出格式

输入格式：

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

 

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

 

输出格式：

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

 

输入输出样例

输入样例#1：

3
1
3
6

输出样例#1：

2
7
44

说明

样例部分解释:

长度为1时只有”A”和“B“两种排列,都是合法的

长度为3时除了”AAA”是不合法的其他都是可以的，故有$ 2^3-1$种

 

数据范围

对于20%数据,全部$ N\le 20,M\le 2$

 

对于70%数据,全部$ N\le 10^7$

 

对于100%数据,全部$ N\leq 10^9,M\leq 10$

 

命题人：Rye_Catcher ←%%%

题解：

    看到1e9的范围后假装自己没有看到，考虑DP。

    因为两个B之间的距离不能超过2，而A的话限制不够简洁明显，因此我们考虑用f[i]表示前i位的合法方案。

    阶段性分析：对于一个f[i]，如果它合法，那么它的最后3个一定不全是’A’。f[i]就可以从f[i-3],f[i-2],f[i-1]转移过来，转移k(k∈[i-3,i-1])时就当作是在k+1的位置放上了一个’B’。因此状态f[i]表示也可以理解为在i+1位置上放一个’B’的方案数(因为前i个合法，所以在i+1位置上放一个’B’一定也合法)，也就是转移了分别在i-2,i-1,i位置上放了B的方案数，因此保证了没有连续3个’A’的合法性。

    状态转移方程就是f[i]=f[i-1]+f[i-2]+f[i-3]。1e9的数据只需要矩阵加速递推就可以了，矩阵长这个样：$$\begin{bmatrix}f[i]\\ f[i-1]\\ f[i-2]\end{bmatrix}=\begin{bmatrix}f[i-1]\\ f[i-2]\\ f[i-3]\end{bmatrix}\times \begin{bmatrix}1 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\end{bmatrix}$$

    联系样例，手推出前三个f[i]就可以了。

    记得开long long。

Code：

#include<cstdio>
#include<cstring>
const int p=19260817;
struct matrix//矩阵部分
{
    long long a[5][5];
    int x,y;
    matrix(int x,int y)
    {
        this->x=x;
        this->y=y;
        memset(a,0,sizeof(a));
    }
    matrix()
    {
        memset(a,0,sizeof(a));
    }
    matrix cross(matrix a,matrix b)
    {
        matrix m(a.x,b.y);
        for(int i=1;i<=m.x;i++)
            for(int j=1;j<=m.y;j++)
            {
                for(int k=1;k<=a.y;k++)
                    m.a[i][j]+=a.a[i][k]*b.a[k][j]%p;
                m.a[i][j]%=p;
            }
        return m;
    }
    void square()
    {
        matrix m(x,y);
        for(int i=1;i<=x;i++)
            for(int j=1;j<=y;j++)
            {
                for(int k=1;k<=x;k++)
                    m.a[i][j]+=a[i][k]*a[k][j]%p;
                m.a[i][j]%=p;
            }
        *this=m;
    }
    matrix qpow(long long t)
    {
        matrix m=*this;
        matrix ans(x,y);
        for(int i=1;i<=x;i++)
            ans.a[i][i]=1;
        while(t)
        {
            if(t&1)
                ans=cross(ans,m);
            m.square();
            t>>=1;
        }
        return ans;
    }
};
int main()
{
    int t,u;
    scanf("%d",&t);
    matrix m(3,3);
    matrix n(3,1);
    m.a[1][1]=1;
    m.a[1][2]=1;
    m.a[1][3]=1;
    m.a[2][1]=1;
    m.a[3][2]=1;
    n.a[1][1]=7;
    n.a[2][1]=4;
    n.a[3][1]=2;
    for(int i=1;i<=t;i++)
    {
        scanf("%d",&u);
        if(u<=3)
        {
            printf("%d\n",n.a[4-u][1]);
            continue;
        }
        matrix ans=m.qpow(u-3);
        ans=ans.cross(ans,n);
        printf("%d\n",ans.a[1][1]);
    }
    return 0;
}