@codeforces - 1106F@ Lunar New Year and a Recursive Sequence

@description@
@solution@
@accepted code@
@details@

@description@

定义递推数列 f：

（1）f[1] = f[2] = ... f[k-1] = 1，f[k] 是一个未知量。

（2）f[i] = (f[i-1]^b[1]) * (f[i-2]^b[2]) * ... *(f[i-k]^b[k]) mod 998244353。

其中 k 和 b[1...k] 是给定的常量。现在已知数列的第 n 项 f[n] = m，求 f[k]。

input

第一行一个整数 k (1 <= k <= 100)。

接下来一行 k 个整数 b1, b2, ..., bk (1 <= bi < 998244353)。

接下来一行两个整数 n, m (k < n <= 10^9, 1 <= m < 998244353)。

output

输出 fk 的值。若不存在，输出 -1。若多解，输出任意一个。

sample input

3

2 3 5

4 16

sample output

4

@solution@

首先，我们想要在 fk 与 fn 之间建立关系。

不难猜想到 fn = fk^x，同时这也暗示我们可以将 1 看成 fk^0。

这样的话原本是非线性递推式，就可以变成指数的线性递推式。可以用矩阵快速幂解出 x 的值。

现在，我们已知 fk^x = fn = m mod 998244353，想要解出 fk 的值。

这是一个经典的数论问题：高次剩余。它有一些复杂的方法，但是对于这个特殊的模数，我们还有一种较为简洁的方法：利用原根。

根据原根的性质，我们可以将任意一个数写成原根的幂的形式。这样上面的式子就会变为 g^(px) = g^q mod 998244353。

通过 BSGS 可以快速解出 q 的值。这样我们只需要根据指数相等列出同余方程用 exgcd 解出 p 的值就可以解决此题了。

@accepted code@

#include<cstdio>

#include<vector>

#include<cmath>

using namespace std;

const int MAXK = 100 + 5;

const int MOD = 998244353;

const int MODPW = MOD - 1;

const int HASHSIZE = 1000037;

struct node{

	int ind, key;

	node(int _i=0, int _k=0):ind(_i), key(_k){}

};

vector<node>h[HASHSIZE];

void hash_insert(int n, int x) {

	h[x%HASHSIZE].push_back(node(n, x));

}

int hash_search(int x) {

	int y = x%HASHSIZE;

	for(int i=0;i<h[y].size();i++)

		if( h[y][i].key == x ) return h[y][i].ind;;

	return -1;

}

void hash_clear() {

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

		h[i].clear();

}

struct matrix{

	int m[MAXK][MAXK];

	int r, c;

}A, B;

matrix operator * (matrix A, matrix B) {

	matrix C; C.r = A.r, C.c = B.c;

	for(int i=0;i<C.r;i++)

		for(int j=0;j<C.c;j++) {

			C.m[i][j] = 0;

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

				C.m[i][j] = (C.m[i][j] + 1LL*A.m[i][k]*B.m[k][j]%MODPW)%MODPW;

		}

	return C;

}

matrix mpow(matrix A, int p) {

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

	for(int i=0;i<ret.r;i++)

		for(int j=0;j<ret.c;j++)

			ret.m[i][j] = (i == j);

	while( p ) {

		if( p & 1 ) ret = ret*A;

		A = A*A;

		p >>= 1;

	}

	return ret;

}

int solve1() {

	int k, n; scanf("%d", &k);

	for(int i=0;i<k;i++) scanf("%d", &A.m[k-1][k-i-1]);

	A.r = A.c = B.r = k; B.c = 1;

	for(int i=0;i<k;i++) B.m[i][0] = 0;

	B.m[k-1][0] = 1;

	for(int i=0;i<k-1;i++)

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

			A.m[i][j] = 0;

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

	scanf("%d", &n); B = mpow(A, n-k)*B;

	return B.m[k-1][0];

}

int pow_mod(int b, int p, int mod) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%mod;

		b = 1LL*b*b%mod;

		p >>= 1;

	}

	return ret;

}

int BSGS(int a, int b) {

	hash_clear();

	int m = int(ceil(sqrt(MOD))), tmp = 1, tmp2;

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

		if( i == m ) tmp2 = tmp;

		hash_insert(i, 1LL*tmp*b%MOD);

		tmp = 1LL*tmp*a%MOD;

	}

	tmp = tmp2;

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

		if( hash_search(tmp) != -1 ) {

			return i*m - hash_search(tmp);

		}

		tmp = 1LL*tmp*tmp2%MOD;

	}

}

typedef long long ll;

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

	if( b == 0 ) {

		x = 1, y = 0;

		return a;

	}

	else {

		ll x1, y1;

		ll d = exgcd(b, a%b, x1, y1);

		x = y1;

		y = x1 - a/b*y1;

		return d;

	}

}

int solve2(int a, int p) {

	int b = BSGS(3, a);

	ll x, y, d = exgcd(p, MODPW, x, y);

	if( b % d ) return -1;

	else {

		x = (1LL*x*b/d%MODPW + MODPW)%MODPW;

		return pow_mod(3, x, MOD);

	}

}

int main() {

	int m, p = solve1(); scanf("%d", &m);

	printf("%d\n", solve2(m, p));

}

@details@

WC2019 讲了“简单”数论，所以就记住了这一算法，然后没想到这一次就用到了。

然而我并没有写过 BSGS，比赛的时候现学的（又是这样嘛……上一次 manacher 也是比赛的时候现学的……）

所以打 CF 还是有用的 2333。

靠着 CF 官方评测系统出锅，续了 40 min，终于把这道题写出来了。

人生第一次 AK。感谢 CF 的评测系统。

只不过 unrated 有点儿可惜 www。

本次比赛好像就这道题有点儿意思（因为是没有写过的新知识）。

A：大模拟

B：英语阅读理解 + 大模拟

C：常见贪心结论

D：一个关于图论的简单贪心

E：英语阅读理解 + 简单 dp

巴特西

@codeforces - 1106F@ Lunar New Year and a Recursive Sequence

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章