P2044 题解

__vector__ · 2022-05-16 21:57:22 · 个人记录

前言：

当年的国赛题目现在居然变成了一个绿题
本题解只是我的做题思路，还没实际写代码测试，可能有错。

题目分析：

题目给定的是一个递推式，序列里一个数由上一个数生成。而且数据范围特别大，要求第 10^{18} 项，不难想到通过矩阵加速来解决这道题。
设两个矩阵：

现在要构造出一个矩阵 B，使得 A \cdot B = C
因为 x_1 = x_{0} \cdot a + c \cdot 1，所以矩阵 A 的第一行为：[a,1]。
因为 c = x_0 \cdot 0 + c \cdot 1，所以矩阵 A 的第二行为 [0,1]
也就是说：

现在构造出了矩阵，那么非常的显然，答案就是：A^{n} \cdot B，矩阵快速幂即可。 算了我对“显然”解释一下：第 n 项是由第 n-1 项 乘矩阵 A 得来的，不能理解手动推算一下就能的出来。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    ll n,m,a,c,x0,g;
    struct Matrix
    {
        ll imap[2][2];
        Matrix()
        {
            memset(imap,0,sizeof(imap));
        }
        void init()
        {
            imap[0][0]=imap[1][1]=1;
        }
        ll guisucheng(ll a,ll b)
        {
            ll res=0;
            while(b)
            {
                if(b&1)res=(res+a)%m;
                a=a*2%m;
                b>>=1;
            }
            return res;
        }
        Matrix operator*(Matrix b)
        {
            Matrix res;
            for(int i=0;i<2;i++)
            {
                for(int j=0;j<2;j++)
                {
                    for(int k=0;k<2;k++)
                    {
                        res.imap[i][j]+=guisucheng(imap[i][k],b.imap[k][j]);
                        res.imap[i][j]%=m;
                    }
                }
            }
            return res;
        }
    };
    Matrix ksm(Matrix base,ll b)
    {
        Matrix res;
        res.init();
        while(b)
        {
            if(b&1)res=res*base;
            base=base*base;
            b>>=1;
        }
        return res;
    }
    Matrix A,B;
    void main()
    {
        scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
        A.imap[0][0]=a;
        A.imap[0][1]=A.imap[1][1]=1;
        B.imap[0][0]=x0;
        B.imap[1][0]=c;
        Matrix ans=ksm(A,n)*B;
        printf("%lld",ans.imap[0][0]%g);
    }
}
int main()
{
    Main::main();
    return 0;
}