CF1106F Lunar New Year and a Recursive Sequence—

题意

设 $$f_i = \left\{\begin{matrix}
1 , \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i < k\\
\prod_{j=1}^k f_{i-j}^{b_j} \ mod \ p, \ \ \ \ \ i > k
\end{matrix}\right.$$

求 $f_k$（$1 \leq f_k < p$），使得 $f_m = n$.（$1 \leq k\leq 100$）

分析

$f_n$ 可以表示成 ${f_k}^x$ 的形式，也就是指数的线性递推式，用矩阵快速幂求出最终 $f_n$ 中的次数就行了。

$$\begin{bmatrix} f_k\\ f_{k-1}\\ \vdots \\ f_1 \end{bmatrix} =
\begin{bmatrix} b_1 & b_2 & \cdots & b_k\\ 1 & 0 & 0 & 0\\ \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 1 & 0 \end{bmatrix} \cdot
\begin{bmatrix} f_{k-1}\\ f_{k-2}\\ \vdots \\ f_0 \end{bmatrix}$$

即 $F_n = B\cdot F_{n-1} = B^{n-k}F_k$

那么就是 ${f_k}^x \equiv f_n \ (mod p) $ 形式了，其中 $x$ 是已经用矩阵快速幂算出来的。

于是就是关于形如 $x^a\equiv b\pmod{p}$ 方程的求解，直接用模板。

其中998244353的原根为3，算常识了吧。

注意算矩阵快速幂时，模并不是 $p$，由欧拉定理，模是 $p-1$.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct matrix

{

    int r, c;

    ll mat[][];

    matrix(){

        memset(mat, , sizeof(mat));

    }

};

const ll p = ;

int k, b[], n, m;

matrix mul(matrix A, matrix B, ll p)   //矩阵相乘

{

    matrix ret;

    ret.r = A.r; ret.c = B.c;

    for(int i = ;i < A.r;i++)

        for(int k = ;k < A.c;k++)

            for(int j = ;j < B.c;j++)

            {

                ret.mat[i][j] = (ret.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % p;

            }

    return ret;

}

matrix mpow(matrix A, int n, int p)

{

    matrix ret;

    ret.r = A.r; ret.c = A.c;

    for(int i = ;i < ret.r;i++)  ret.mat[i][i] = ;

    while(n)

    {

        if(n & )  ret = mul(ret, A, p);

        A = mul(A, A, p);

        n >>= ;

    }

    return ret;

}

ll gcd(ll a, ll b)

{

    return b ? gcd(b, a%b) : a;

}

ll qpow(ll a, ll b, ll p)

{

    a = a % p;

    ll ret = ;

    while(b)

    {

        if(b&)  ret = ret * a % p;

        a = a * a %p;

        b >>= ;

    }

    return ret % p;

}

map<int,int>mp;

int bsgs(int a, int b, int p){    //a^x = b (mod P),(a,p)=1，返回x,x>=1

    int m=sqrt(p)+;mp.clear();

    for(register int i=,res=b;i<m;++i,res=1ll*res*a%p)mp[res]=i;

    for(register int i=,tmp=qpow(a,m,p),res=tmp;i<=m+;++i,res=1ll*res*tmp%p)

        if(mp.count(res))return i*m-mp[res];

    return -;

}

int  main()

{

    scanf("%d", &k);

    for(int i = ;i <= k;i++)  scanf("%d", &b[i]);

    scanf("%d%d", &n, &m);

    matrix B;

    B.r = B.c = k;

    for(int i = ;i < k;i++)  B.mat[][i] = b[i+];

    for(int i = ;i < k;i++)  B.mat[i][i-] = ;

    B = mpow(B, n-k, p-);

    int a = B.mat[][] % (p-);    //注意，是模p-1 而非p

    int c = bsgs(qpow(, a, p), m, p);

    if(c == -)  printf("-1\n");

    else

    {

        int fk = qpow(, c, p);

        printf("%d\n", fk);

    }

}

参考链接：https://www.cnblogs.com/bztMinamoto/p/10348641.html

巴特西

CF1106F Lunar New Year and a Recursive Sequence——矩阵快速幂&&bsgs

题意

分析

最新文章

热门文章