CF1106F Lunar New Year and a Recursive Sequence

发表于 | 阅读数

有一串$n(n\leqslant10^9)$个数的数列，给你$b_1\sim b_k$
$(k⩽100)$。当$i>k$时：

已知$f_1=f_2=\cdots=f_{k-1}=1,f_n=m$
，问最小的正整数$f_k$可能是多少

$x$用个矩阵快速幂求出来就好了。

n次剩余，其实把$f_k=g^y$,g表示原根即$3$.

$m=3^{xy} \mod 998244353$

$BSGS$求出$t=xy\mod (p-1)$

$exgcd$求出$y$即可

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
#define mk make_pair
const ll N = 1e6 + 10;
const ll M = 1e2 + 10;
const ll mod = 998244353;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll gd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gd;
}
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll inv(ll a, ll b) //逆元
{
    ll x, y;
    exgcd(a, b, x, y);
    return (x % b + b) % b;
}

ll qpow(ll a, ll x, ll mo)
{
    ll res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        x >>= 1;
    }
    return res;
}
struct Matrix
{
    ll a[M][M];
    ll n, m;
} e;

Matrix mat_mul(Matrix x, Matrix y, ll P) //实现两个矩阵相乘，返回的还是一个矩阵。
{
    Matrix res; //用来表示得到的新的矩阵；
    memset(res.a, 0, sizeof(res.a));
    res.n = x.n, res.m = y.m;
    for (ll i = 1; i <= res.n; i++)
        for (ll j = 1; j <= res.m; j++)
            for (ll k = 1; k <= x.m; k++)
                res.a[i][j] = (res.a[i][j] + 1ll * x.a[i][k] * y.a[k][j] % P) % P;

    return res;
}

Matrix mqpow(Matrix x, ll y, ll P)
{
    Matrix ans = e;

    while (y)
    {
        if (y & 1)
            ans = mat_mul(ans, x, P);
        x = mat_mul(x, x, P);
        y >>= 1;
    }
    return ans;
}

ll BSGS(ll a, ll b, ll p)
{
    map<ll, ll> mp;
    ll k = sqrt(p) + 1;
    ll tmp = b;
    ll pa = 1;
    for (ll i = 1; i <= k; i++)
    {
        tmp = 1ll * tmp * a % p;
        pa = 1ll * pa * a % p;
        mp[tmp] = i;
    }
    ll now = 1;
    for (ll i = 1; i <= k; i++)
    {
        now = 1ll * now * pa % p;
        if (mp[now])
        {
            return (i * k - mp[now] + 2 * p) % p;
        }
    }
    return -1;
}

ll b[N];
int main()
{
    ll k, n, m;
    cin >> k;
    for (ll i = 1; i <= k; i++)
        cin >> b[i];
    for (ll i = 1; i <= k; i++)
        e.a[i][i] = 1;
    cin >> n >> m;
    Matrix xx;
    xx.n = xx.m = e.n = e.m = k;
    for (ll i = 1; i <= k; i++)
        xx.a[1][i] = b[i] % (mod - 1);
    for (ll i = 1; i < k; i++)
        xx.a[i + 1][i] = 1;
    Matrix yy;
    yy.n = k, yy.m = 1;
    for (ll i = 1; i <= k; i++)
        yy.a[i][1] = 0;
    yy.a[1][1] = 1;
    //Matrix res = mqpow(xx, n - k, mod - 1);

    ll res = mat_mul(mqpow(xx, n - k, mod - 1), yy, mod - 1).a[1][1];

    {
        ll ans = BSGS(3, m, mod);
        if (ans == -1)
            puts("-1");
        else
        {
            if (ans % gcd(mod - 1, res))
            {
                puts("-1");
            }
            else
            {

                ll x, y;
                exgcd(res, mod - 1, x, y);
                x = ((x % (mod - 1) + mod - 1) % (mod - 1)) * (ans / gcd(mod - 1, res)) % (mod - 1);
                cout << qpow(3, x, mod) << endl;
            }
        }
    }
}