CF1106F Lunar New Year and a Recursive Sequence 原根、矩阵快速幂、BSGS

好久没写数论题了写一次调了1h

首先发现递推式是一个乘方的形式，线性递推和矩阵快速幂似乎都做不了，那么是否能够把乘方运算变成加法运算和乘法运算呢？

使用原根！学过\(NTT\)的都知道\(998244353\)的原根\(G=3\)。

使用原根之后，可以得到一个等价的新递推式：\(G^{g_i} = \prod\limits _ {j=1}^k G^{g_{i - j} \times b_j} \mod 998244353(G^{g_i} \equiv f_i\mod 998244353)\)，它等价于\(g_i = \sum\limits_{j=1}^k g_{i-j} \times b_j \mod 998244352\)。这样就可以矩阵快速幂得出当\(f_k\)等于某个值\(G^p\)时\(f_n\)的值了。

可现在知道的是\(f_n\)的值，不知道\(f_k\)的值。

考虑：令\(G_k=1\)，得到\(G_n\)的值\(x\)，那么可以知道\(f_k^x \equiv f_n \mod 998244353\)。

这是一个模意义下的高次剩余方程，要怎么求解呢？

同样使用原根。设\(f_{k} = G^b \mod 998244353\)，通过\(BSGS\)求出\(f_n = G^y \mod 998244353\)，那么原式变成\(G^{bx} \equiv G^y \mod 998244353\)，即\(bx \equiv y \mod 998244352\)。逆元求解方程得到\(b\)，也就得到了\(f_k\)。

一些打比赛时被坑到的点：

①\(998244352 = 2^{23} \times 7 \times 17\)，求逆元要用欧拉定理或者拓展欧几里得

②\(998244351 \times 998244351 \times 100 > 2^{63}\)，这意味着矩阵相乘不能算完再一起取模

#include<bits/stdc++.h>

#define int long long

//This code is written by Itst

using namespace std;

inline int read(){

    int a = 0;

    char c = getchar();

    bool f = 0;

    while(!isdigit(c)){

	    if(c == '-')

			f = 1;

        c = getchar();

    }

    while(isdigit(c)){

		a = (a << 3) + (a << 1) + (c ^ '0');

		c = getchar();

	}

	return f ? -a : a;

}

const int MOD = 998244353 , G = 3;

int K;

struct matrix{

	int a[100][100];

	int* operator [](int x){return a[x];}

	matrix(){memset(a , 0 , sizeof(a));}

	matrix operator *(matrix b){

		matrix c;

		for(int i = 0 ; i < K ; ++i)

			for(int j = 0 ; j < K ; ++j)

				for(int k = 0 ; k < K ; ++k)

					c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % (MOD - 1);

		return c;

	}

}S , T;

inline int gcd(int a , int b){

	int r = a % b;

	while(r){

		a = b;

		b = r;

		r = a % b;

	}

	return b;

}

inline int poww(int a , int b , int mod = MOD){

	int times = 1;

	while(b){

		if(b & 1)

			times = times * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return times;

}

map < int , int > Hash;

inline int BSGS(int x){

	int t = sqrt(MOD) + 1 , times = x;

    for(int i = 0 ; i < t ; i++){

        Hash[times] = i;

        times = times * G % MOD;

    }

    times = poww(G , t);

    int now = times;

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

        if(Hash.count(now)){

            return i * t - Hash[now];

        }

        now = now * times % MOD;

    }

	return -1;

}

int phi(int x){

	int times = x;

	for(int i = 2 ; i * i <= x ; ++i){

		if(x % i == 0){

			times = times / i * (i - 1);

			while(x % i == 0)

				x /= i;

		}

	}

	if(x - 1)

		times = times / x * (x - 1);

	return times;

} 

signed main(){

	#ifndef ONLINE_JUDGE

	//freopen("in" , "r" , stdin);

	//freopen("out" , "w" , stdout);

	#endif

	K = read();

	for(int i = 0 ; i < K ; ++i)

		T[K - i - 1][K - 1] = read() % (MOD - 1);

	int N = read() - K;

	int t = BSGS(read());

	for(int i = 0 ; i + 1 < K ; ++i)

		T[i + 1][i] = 1;

	S[0][K - 1] = 1;

	while(N){

		if(N & 1)

			S = S * T;

		T = T * T;

		N >>= 1;

	}

	int cur = S[0][K - 1] , p = gcd(cur , MOD - 1);

	if(t % p != 0)

		puts("-1");

	else{

		t /= p;

		cur /= p;

		int mod = (MOD - 1) / p;

		cout << poww(G , poww(cur , phi(mod) - 1 , mod) * t % mod);

	}

	return 0;

}

巴特西

CF1106F Lunar New Year and a Recursive Sequence 原根、矩阵快速幂、BSGS

最新文章

热门文章