牛客多校第五场

B:generator 1

题意

给你$x0,x_1,a,b, x_i=ax{i-1}+bx_{i-2}$让你求出$x_n$

思路

典型的矩阵快速幂,但是n的范围太大,所以得快速幂得用十进制快速幂

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
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e6 + 5;
ll mod;

struct Matrix{
ll mat[2][2];

Matrix() {memset(mat, 0, sizeof(mat));};

void init() {
mat[0][0] = mat[1][1] = 1;
}

void init(ll a, ll b) {
mat[0][0] = 0; mat[0][1] = b;
mat[1][0] = 1; mat[1][1] = a;
}

void operator = (Matrix x) {
for (int i = 0; i <= 1; i ++)
for (int j = 0; j <= 1; j ++)
mat[i][j] = x.mat[i][j];
}

};

void Print(Matrix x) {
for (int i = 0; i <= 1; i ++) {
for (int j = 0; j <= 1; j ++)
cout << x.mat[i][j] << " ";
cout << endl;
}
}

Matrix operator * (Matrix x, Matrix y) {
Matrix t;
for (int i = 0; i <= 1; i ++)
for (int j = 0; j <= 1; j ++)
for (int k = 0; k <= 1; k ++)
t.mat[i][j] = (t.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;
return t;
}

Matrix Ksm(Matrix x, ll b) {
//cout << b << endl;
Matrix t; t.init();
while(b) {
if(b & 1) t = t * x;
x = x * x;
b >>= 1;
}
//Print(t);
return t;
}


int main() {
ll x0, x1, a, b;
scanf("%lld %lld %lld %lld", &x0, &x1, &a, &b);
char s[maxn];
scanf("%s%lld", s, &mod);
int len = strlen(s);
reverse(s, s+len);
Matrix t, ans; t.init(a, b);
ans.mat[0][0] = x0; ans.mat[0][1] = x1;
Matrix res;
res.init();
for (int i = 0; i < len; i ++) {
res = res * Ksm(t, s[i]-'0');
t = Ksm(t, 10);
// Print(res);
// Print(t);
}
ans = ans * res;
printf("%lld\n", ans.mat[0][0]);
return 0;
}

C:generator 2

题意

有这么一个递推式$xi=(a\cdot x{i-1}+b)\mod p$,让你求$v$在$[1,n-1]$中第一次出现的位置

思路

因为递推式模$p$,所以$x$的循环节一定小于$p$,

而$x$又是这种形式$x_n=a(a(a(ax+b)+b)+b)+b$

所以我们的任务就变成$A^{m} \equiv v\mod p$求最小的$m$

${A^1=x,A^2=(ax+b),A^3=a(ax+b)+b,A^4=a(a(ax+b)+b)+b)+b}$

而$A^m\equiv v\mod p$明显可以用BSGS

但是BSGS的一个使用条件能不能求出$A^{-i*S}$

但是我们怎么求出$A^{-i*S}$呢

正常的加是乘a加b,那么除就是除a减$\frac{b}{a}$

举个例子:

$x_0=x,x_1=ax+b,x_2=a(ax+b)+b,x_3=a(a(ax+b)+b)+b$

我们从$x_3$降到$x_1$,$x_3$先除$a$再减去$\frac{b}{a}$变成$x_2$,然后再除$a$减去$\frac{b}{a}$变成$x_1$

那我们从$A^{2S+j}$降到$A^{S+j}$只需要进行$S$次操作即可

这样我们就可以用BSGS了

跟BSGS的步骤差不多,我们可以把式子化成 $A^{i*S+j}\equiv v\mod p$

我们可以预处理出来$A^S$ ,然后遍历找到一个$A^j\equiv vA^{-iS}\mod p$

也就是说在这个式子中$A^{-i*S}$不是一个值,而是一种操作,把$v$所代表的次数降下$S$

$x_0=1,x_1=2*1+1,x_2=,x_4=15,x_5=31$

因为我们已经预处理了一个$A^S$,那么在我们遍历$i$的过程中每次降下一个$S$,知道找到或者找不到

用Hash存一下$A^j$

AC代码

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pis;
const int limit = 1e6;
pis d[limit+6];
int vals[limit+6], pos[limit+6];

int Ksm(ll a, int b, int p) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

int inv(int a, int p) { return Ksm(a, p-2, p); }

void solve() {
ll n, x0, a, b, p; int Q;
scanf("%lld %lld %lld %lld %lld %d", &n, &x0, &a, &b, &p, &Q);
if(!a) {
while(Q --) {
int v; scanf("%d", &v);
if(v == x0) printf("0\n");
else if(v == b) printf("1\n");
else printf("-1\n");
}
return ;
}
d[0] = {x0, 0};
for (int i = 1; i <= limit; i ++) {
int val = (a*d[i-1].first+b) % p;
d[i] = {val, i};
}
sort(d, d+limit+1);
int cnt = 0;
for (int i = 0; i <= limit; i ++) {
vals[cnt] = d[i].first; pos[cnt++] = d[i].second;
while(d[i].first == d[i+1].first && i+1 <= limit) i++;
}
int inv_a = inv(a, p);
int inv_b = (p-b) % p * inv_a % p;
ll aa = 1, bb = 0;
for (int i = 0; i <= limit; i ++) {
aa = aa * inv_a % p;
bb = (bb * inv_a + inv_b) % p;
}
while(Q --) {
int v; scanf("%d", &v);
int it = lower_bound(vals, vals+cnt, v) - vals;
if(it < cnt && vals[it] == v) {
if(pos[it] < n) printf("%d\n", pos[it]);
else printf("-1\n");
continue;
}
int m = p/(limit+1) + 3, flag = 0;
for (int i = 1; i <= m; i ++) {
v = (aa * v + bb) % p;
it = lower_bound(vals, vals+cnt, v) - vals;
if(it<cnt && vals[it] == v) {
flag = 1;
int res = i*(limit+1)+pos[it];
if(res>=n) res = -1;
printf("%d\n", res);
break;
}
}
if(!flag) printf("-1\n");
}
}

int main() {
int T;
scanf("%d", &T);
while(T --) solve();
return 0;
}
---------Thanks for your attention---------