2019ACM-ICPC南昌网络赛

H: The Nth Item

题意

$F(0)=0,F(1)=1$

$F(n)= 3\times F(n-1)+2\times F(n-2)(n\ge 2)$

求第n项,n个询问,强制在线

思路

好像直接1e6进制矩阵快速幂就可以直接过,预先打个1e6的表,但这个好像是卡过,多交几次就会T掉

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
const int maxn = 1e6;
const int ll mod = 998244353;

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];
}

};

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 pre[4][2*maxn+10];

ll Ksm(ll b) {
Matrix t; t.init();
int cnt = 0;
while(b && cnt < 3) {
++ cnt;
ll pt = b % maxn;
if(cnt == 3) pt = b;
t = t * pre[cnt][pt];
b /= maxn;
}
Matrix ans;
ans.mat[0][0] = 0; ans.mat[0][1] = 1;
ans = ans * t;
return ans.mat[0][0];
}

void init() {
Matrix t; t.init(3, 2);
pre[1][1] = t; pre[1][0].init();
for (int i = 2; i <= maxn; i ++) pre[1][i] = pre[1][i-1] * pre[1][1];
pre[2][1] = pre[1][maxn]; pre[2][0].init();
for (int i = 2; i <= maxn; i ++) pre[2][i] = pre[2][i-1] * pre[2][1];
pre[3][1] = pre[2][maxn]; pre[3][0].init();
for (int i = 3; i <= 2* maxn; i ++) pre[3][i] = pre[3][i-1] * pre[3][1];
}

int main() {
init();
ll n, q;
scanf("%lld %lld", &n, &q);
ll ans = 0;
for (int i = 1; i <= n; i ++) {
ll a = Ksm(q);
q = q ^ (a * a);
ans ^= a;
}
printf("%lld\n", ans);
return 0;
}

思路

还有一种解法,通过打表得知询问$q$是由循环节的,最后在进行大约$1e6$次后,会有一个长度为$2$的循环节,我们就直接暴力找循环节,时间上好像比上面快一点

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

#define ll long long
const ll mod = 998244353;

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];
}

};

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;
}

ll Ksm(ll b) {
Matrix x; x.init(3, 2);
Matrix t; t.init();
while(b) {
if(b & 1) t = t * x;
x = x * x;
b >>= 1;
}
Matrix ans;
ans.mat[0][0] = 0; ans.mat[0][1] = 1;
ans = ans * t;
return ans.mat[0][0];
}
map<ll, int> mp;

int main() {
ll n, q;
scanf("%lld %lld", &n, &q);
ll ans = 0, l, r, loop=-1;
for (int i = 1; i <= n; i ++) {
if(mp[q]) {
loop = i-1;
l = q;
ll a = Ksm(q);
r = q ^ (a * a);
break;
}
mp[q] = 1;
ll a= Ksm(q);
q = q ^ (a * a);
ans = ans ^ a;
}
if(loop!=-1) {
ll dis = n - loop;
if(dis % 4 == 3) ans = ans ^ Ksm(r);
if(dis % 4 == 2) ans = ans ^ Ksm(l) ^ Ksm(r);
if(dis % 4 == 1) ans = ans ^ Ksm(l);
}
printf("%lld\n", ans);
return 0;
}

loop

---------Thanks for your attention---------