Description
有若干个字符串 $s_1$ ~ $s_\infty$，其中 $s_1$ = ‘a‘，$s_2$ = ‘b‘，$s_i = s_{i - 1} + s_{i - 2}$。
定义一个字符串 $S$ 的价值为 $i$ 当且仅当 $i$ 小于 $|S|$ 且 $S[1..i] = S[n - i + 1..n]$，现在给出你 $T$ 组数据，每组数据给出你两个正整数 $n$ 和 $m$，请你对于每组数据求出字符串 $s_n$ 长度为 $m$ 的前缀的价值。
Solution
吉老师的一道有趣的题。
找规律可以发现，如果我们设 $f_i$ 表示斐波那契数列的第 $(i + 1)$ 项，则若 $pos$ 为最小的可以使 $f_{pos} > m + 1$ 的数，则答案为 $(m - f_{pos - 2})$。
证明留作读者练习。
Code
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
148
149
150
151
152
153
154
155
| #include <cstdio>
#include <cstring>
#define mod 258280327LL
#define maxN 1010
char st[710];
int f[maxN][710];
int Ans[710], a[710];
int max (int x, int y)
{
return x > y ? x : y;
}
void work (int x)
{
int A = f[x - 1][0];
int B = f[x - 2][0];
int C = max(A, B);
for(int i = 1;i <= C; i++)
{
f[x][i] = f[x - 1][i] + f[x - 2][i];
}
for(int i = 1;i <= C; i++)
{
if(f[x][i] > 9)
{
f[x][i + 1]++;
if(i + 1 > C)
{
C++;
}
f[x][i] -= 10;
}
}
f[x][0] = C;
}
int main ()
{
f[1][0] = 1;
f[1][1] = 1;
f[2][0] = 1;
f[2][1] = 2;
for(int i = 3;i < maxN; i++)
{
work(i);
}
int T = 0;
int cnt = 0;
scanf("%d", &T);
while(T--)
{
cnt++;
int n = 0;
scanf("%d", &n);
scanf("%s", st + 1);
int A = strlen(st + 1);
for(int i = 1;i <= A; i++)
{
a[i] = st[A - i + 1] - '0';
}
int pos = 0;
a[1]++;
for(int i = 1;i <= A; i++)
{
if(a[i] > 9)
{
a[i + 1]++;
a[i] -= 10;
if(i + 1 > A)
{
A++;
}
}
}
for(int x = 1;x < maxN; x++)
{
int B = f[x][0];
if(A == B)
{
bool flag = false;
for(int i = A;i >= 1; i--)
{
int nowA = a[i];
int nowB = f[x][i];
if(i == 1)
{
if(nowB > nowA)
{
flag = true;
break;
}
}
else
{
if(nowB > nowA)
{
flag = true;
break;
}
else if(nowB < nowA)
{
break;
}
}
}
if(flag)
{
pos = x - 2;
break;
}
}
else if(A < B)
{
pos = x - 2;
break;
}
}
a[1]--;
for(int i = 1;i <= A; i++)
{
if(a[i] < 0)
{
a[i + 1]--;
a[i] += 10;
}
}
while(!a[A] && A >= 2)
{
A--;
}
for(int i = A;i >= 1; i--)
{
Ans[i] = a[i] - f[pos][i];
a[i] = 0;
}
for(int i = 1;i <= A; i++)
{
if(Ans[i] < 0)
{
Ans[i + 1]--;
Ans[i] += 10;
}
}
while(!Ans[A] && A >= 2)
{
A--;
}
long long res = 0;
for(int i = A;i >= 1; i--)
{
res = res * 10LL + Ans[i];
res %= mod;
}
printf("%lld\n", res);
}
return 0;
}
|