要点
- 998244353的原根g = 3，意味着对于任意$$1 <= x,y<p$$$$x\neq\ y$$$$gy%p$$因此可以有构造序列\(q(a)与a一一对应，g^{q(a)}\%p=a\)。那么对应到这道题上，因为\(f_i\)是%p的，所以构造\(h_i\)序列，使得$$g{k}(f_{i-j}){\sum_{j=1}^k{h_{i-j}\times\ b_j}}%p$$$$\because 原根的唯一对应性质且g^{p-1}%p=1$$$$\therefore h_i\equiv \sum_{j=1}^kh_{i-j}\times b_j(mod\ p-1)$$
- 以上就是本题全部关键了，接下来就是数论复习内容了。
- 首先看到这个熟悉的式子想到我们可以\(\%(p-1)\)意义下矩阵快速幂求解，往常是给前面的项求第n项，这次是有\(h_n\)求\(h_k\)。
- 其中\(h_n\)的求法是BSGS算法
- 矩阵快速幂以后，因为题面说初始除了\(f_k\)以外都是1，所以\(h_{1…k-1}\)都是0，故而有$$h_n\equiv Matrix[0][0]\times h_k(mod\ p-1)$$
- 这就变成了\(ah_x\equiv c(\%b)\)，变形为\(ax+by=c\)即可用扩展欧几里得求解，若有解，用快速幂求得\(f_k\)，否则输出-1.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int p = 998244353, g = 3;
int K, b[101], n, fn, hn, hk;
struct Matrix {
int n;
int v[101][101];
Matrix(int n) { memset(v, 0, sizeof v); this->n = n; }
friend Matrix operator * (Matrix A, Matrix B) {
int n = A.n;
Matrix ret(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) {
ret.v[i][j] = ((ll)ret.v[i][j] + (ll)A.v[i][k] * B.v[k][j] % (p - 1)) % (p - 1);
}
return ret;
}
friend Matrix operator ^ (Matrix A, int k) {
int n = A.n;
Matrix ret(n);
for (int i = 0; i < n; i++)
ret.v[i][i] = 1;
for (; k; k >>= 1) {
if (k & 1) ret = ret * A;
A = A * A;
}
return ret;
}
};
namespace BSGS {
const int maxm = 1e5 + 1000;
int hash_table[maxm], val[maxm];
int ksm(int a, int b, int mod) {
int res = 1;
for (; b; b >>= 1) {
if (b & 1) res = (ll)res * a % mod;
a = (ll)a * a % mod;
}
return res;
}
int find(int n) {
int id = n % maxm;
while (hash_table[id] >= 0 && hash_table[id] != n)
id = (id + 1) % maxm;
return id;
}
int bsgs(int a, int b, int p) {
a %= p, b %= p;
if (!a) return b ? -1 : 1;
memset(hash_table, -1, sizeof hash_table);
int m = sqrt(p) + 1;
int now = b;
hash_table[now % maxm] = now;
val[now % maxm] = 0;
for (int i = 1; i <= m; i++) {
now = (ll)now * a % p;
int pos = find(now);
hash_table[pos] = now;
val[pos] = i;
}
int t = ksm(a, m, p);
now = 1;
for (int i = 1; i <= m; i++) {
now = (ll)now * t % p;
int pos = find(now);
if (hash_table[pos] >= 0) {
return i * m - val[pos];
}
}
return -1;
}
}
namespace EXGCD {
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll q = exgcd(b, a % b, y, x);
y -= a / b * x;
return q;
}
int solve(int a, int b, int c) {//ax = c (% b)求x的解
if (!c) return 0;
int q = gcd(a, b);
if (c % q) return -1;
a /= q, b /= q, c /= q;
ll ans, __;
exgcd((ll)a, (ll)b, ans, __);
ans = (ans * c % b + b) % b;
return ans;
}
}
int main() {
scanf("%d", &K);
for (int i = 0; i < K; i++)
scanf("%d", &b[i]), b[i] %= p - 1;
scanf("%d%d", &n, &fn);
hn = BSGS::bsgs(g, fn, p);
Matrix A(K);
for (int i = 0; i < K; i++)
A.v[0][i] = b[i];
for (int j = 1; j < K; j++)
A.v[j][j - 1] = 1;
A = A ^ (n - K);
hk = EXGCD::solve(A.v[0][0], p - 1, hn);
if (hk >= 0) {
printf("%d\n", BSGS::ksm(g, hk, p));
} else {
printf("-1\n");
}
return 0;
}