/
1269.test.cpp
55 lines (50 loc) · 1019 Bytes
/
1269.test.cpp
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
#define PROBLEM "https://yukicoder.me/problems/no/1269"
#include "my_template.hpp"
#include "other/io.hpp"
#include "string/trie.hpp"
#include "mod/modint.hpp"
using mint = modint107;
void solve() {
LL(N, L, R);
vi F = {1, 2};
while (F.back() <= R) F.eb(F[len(F) - 2] + F[len(F) - 1]);
{
vi tmp;
for (auto&& x: F)
if (L <= x && x <= R) tmp.eb(x);
F = tmp;
}
Trie<10> X;
for (auto&& f: F) {
string s = to_string(f);
X.add(s, '0');
}
X.calc_suffix_link(1);
ll n = X.n_node;
vc<bool> ng(n);
for (auto&& v: X.words) ng[v] = 1;
for (auto&& v: X.BFS)
if (v) {
int p = X.suffix_link[v];
if (ng[p]) ng[v] = 1;
}
vc<mint> dp(n);
dp[0] = 1;
FOR(N) {
vc<mint> newdp(n);
FOR(v, n) {
FOR(d, 10) {
int to = X.TO[v][d];
if (ng[to]) continue;
assert(0 <= to && to < n);
newdp[to] += dp[v];
}
}
swap(dp, newdp);
}
print(SUM<mint>(dp) - mint(1));
}
signed main() {
solve();
return 0;
}