Codeforces Round #536 (Div. 2) F 矩阵快速幂 + bsgs(新坑) + exgcd(新坑) + 欧拉降幂

https://codeforces.com/contest/1106/problem/F

题意

数列公式为\(f_i=(f^{b_1}_{i-1}*f^{b_2}_{i-2}*...*f^{b_k}_{i-k})\)mod\(P\),给出\(f_{1}...f_{k-1}\)和\(f_{n}\),求\(f_{k}\),其中\(P\)等于998244353

题解

3是998244353的离散对数,所以\(f^{b_1}_{i-1} \equiv 3^{h_i*b_1}(modP)\),怎么求离散对数
乘法转化为加法:\(h_{k+1}\equiv(h_{k}*b_1+...+h_{1}*b_k)mod(P-1)\),矩阵快速幂求出\(h_n\)(\(c*h_k(未知数)\)),\(mod(P-1)\)是欧拉降幂,因为\(h_n\)可能会很大
得到\(f_n=3^{h_n}\equiv m(modP)\),bsgs求出\(h_n\),有空填exbsgs的坑
于是得到\(c*h_k\equiv h_n(modP-1)\)的一元同余方程,用exgcd解出\(h_k\),exgcd还有好多用途
然后\(f_k\equiv3^{h_k}(modP)\)

代码

//vector矩阵快速幂板子

#include<bits/stdc++.h>

#define MOD 998244353

#define ll long long

#define vec vector<ll>

#define mat vector<vec>

using namespace std;

mat mul(mat &A,mat &B,ll mod){

	mat C(A.size(),vec(B[0].size()));

	for(int i=0;i<A.size();i++)

		for(int j=0;j<A.size();j++)

			for(int k=0;k<A.size();k++)

				C[i][j]+=A[i][k]*B[k][j]%mod,C[i][j]%=mod;

	return C;

}

mat pw(mat &A,ll x,ll mod){

	mat C(A.size(),vec(A.size()));

	for(int i=0;i<A.size();i++)C[i][i]=1;

	while(x){

		if(x&1)C=mul(C,A,mod);

		A=mul(A,A,mod);

		x>>=1;

	}

	return C;

}

ll pw(ll bs,ll x,ll mod){

	ll ans=1;

	while(x){

		if(x&1)ans=ans*bs%mod;

		bs=bs*bs%mod;

		x>>=1;

	}

	return ans;

}

ll bsgs(ll a,ll b,ll c){

	ll m=ceil(sqrt(c));

	map<ll,ll>mp;

	ll bs=b,BS=pw(a,m,c);

	for(int i=1;i<=m;i++){mp[bs]=i-1;bs=bs*a%c;}

	bs=1;

	for(int i=1;i<=m;i++){

		if(mp[bs])return (i-1)*m-mp[bs];

		bs=bs*BS%c;

	}

	return -1;

}

ll exgcd(ll a,ll b,ll &x,ll &y){

	ll d=a;

	if(b==0)x=1,y=0;

	else d=exgcd(b,a%b,y,x),y-=x*(a/b);

	return d;

}

ll sol(ll a,ll b,ll m){

	if(b==0)return 0;

	ll g=__gcd(a,m);

	if(b%g)return -1;

	a/=g;b/=g;m/=g;

	ll x,y;

	g=exgcd(a,m,x,y);

	x=x*b%m;

	return (x+m)%m;

}

ll k,n,m,h,ans;

int main(){

	cin>>k;

	mat A(k,vec(k));

	for(int i=0;i<k;i++)cin>>A[i][0];

	for(int i=1;i<k;i++)A[i-1][i]=1;

	cin>>n>>m;

	A=pw(A,n-k,MOD-1);

	h=bsgs(3,m,MOD);

	ans=sol(A[0][0],h,MOD-1);

	if(ans<0)cout<<-1;

	else cout<<pw(3,ans,MOD);

}

巴特西

Codeforces Round #536 (Div. 2) F 矩阵快速幂 + bsgs(新坑) + exgcd(新坑) + 欧拉降幂

题意

题解

代码

最新文章

热门文章