Codeforces 1106F Lunar New Year and a Recursive Sequence

题目链接https://codeforces.com/problemset/problem/1106/F

题意:略。

思路:见https://www.cnblogs.com/reverymoon/p/10344706.html,主要是要掌握求x^n\bmod P=mn的时候如果模数有原根,那么我们可以把x表示成原根的幂次的形式,然后可以用BSGS求得m的幂次然后转化成幂次的同余方程的形式。

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100+10;
const int P=998244353;
int K,n,m,i,j,x,y,yy,t,b[N];
struct matrix{
    #define MS(x,y) memset(x,y,sizeof(x))
    #define MC(x,y) memcpy(x,y,sizeof(x))
    int v[N][N];
    void O(){MS(v,0);}
    void E(){MS(v,0);for(int i = 0; i < K; ++i)v[i][i] = 1; }
    matrix operator*(const matrix &b)const{
        matrix c;c.O();
        for (int k=0;k<K;k++){
            for (int i=0;i<K;i++)if(v[i][k]){
                for (int j=0;j<K;j++){
                    c.v[i][j]=(c.v[i][j]+(ll)v[i][k]*b.v[k][j])%(P-1);
                }
            }
        }
        return c;
    }
    matrix operator^(int p)const{
        matrix y; y.E();
        matrix x; memcpy(x.v,v,sizeof(v));
        while (p){
            if (p&1) y=y*x;
            x=x*x;
            p>>=1;
        }
        return y;
    }
}mat;
int fexp(int a,int n,int mod){
    int res=1;
    while (n){
        if (n&1) res=(ll)res*a%mod;
        a=(ll)a*a%mod;
        n>>=1;
    }
    return res;
}
int baby_step_gaint_step(int a,int b,int p){
    map<int,int>hash;
    hash.clear();
    b%=p;
    int t=(int)sqrt(p)+1;
    for (int j=0;j<t;++j){
        int val=(ll)b*fexp(a,j,p)%p;
        hash[val]=j;
    }
    a=fexp(a,t,p);
    if (a==0) return b==0?1:-1;
    for (int i=0;i<=t;++i){
        int val=fexp(a,i,p);
        int j=hash.find(val)==hash.end()?-1:hash[val];
        if (j>=0 && i*t-j>=0) return i*t-j;
    }
    return -1;
}
int exgcd(int a,int b,int&x,int&y){
    if (!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
int main(){
    read(K);
    for (i=1;i<=K;++i) read(b[i]);
    read(n),read(m);
    for (i=0;i<K;++i) mat.v[0][i]=b[i+1];
    for (i=1;i<K;++i) mat.v[i][i-1]=1;
    mat=mat^(n-K);
    y=mat.v[0][0];
    t=baby_step_gaint_step(3,m,P);
    if (t==-1) return puts("-1"),0;
    int d=exgcd(y,P-1,x,yy);
    if (t%d!=0) puts("-1");
    else{
        x=1LL*x*t/d%(P-1);
        x=(x%(P-1)+(P-1))%(P-1);
        printf("%d\n",fexp(3,x,P));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注