結果
| 問題 | No.1269 I hate Fibonacci Number |
| ユーザー |
 やむなく
|
| 提出日時 | 2020-10-23 23:54:18 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,177 bytes |
| コンパイル時間 | 2,247 ms |
| コンパイル使用メモリ | 187,356 KB |
| 実行使用メモリ | 4,504 KB |
| 最終ジャッジ日時 | 2023-09-28 19:14:47 |
| 合計ジャッジ時間 | 4,139 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
ソースコード
//
// Created by yamunaku on 2020/10/23.
//
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)
using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;
template<int char_size>
struct TrieNode {
int nxt[char_size];
int exist;
ll count;
bool flag;
vector<int> accept;
TrieNode() : exist(0), count(0), flag(false) {
memset(nxt, -1, sizeof(nxt));
}
};
template<int char_size, int margin>
struct Trie {
using Node = TrieNode<char_size>;
vector<Node> nodes;
int root;
Trie() : root(0) {
nodes.push_back(Node());
}
void update_direct(int node, int id) {
nodes[node].accept.push_back(id);
}
void update_child(int node, int child, int id) {
++nodes[node].exist;
}
void add(const string &str, int str_index, int node_index, int id) {
if (str_index == str.size()) {
update_direct(node_index, id);
nodes[node_index].flag = true;
} else {
const int c = str[str_index] - margin;
if (nodes[node_index].nxt[c] == -1) {
nodes[node_index].nxt[c] = (int) nodes.size();
nodes.push_back(Node());
}
add(str, str_index + 1, nodes[node_index].nxt[c], id);
update_child(node_index, nodes[node_index].nxt[c], id);
}
}
void add(const string &str, int id) {
add(str, 0, 0, id);
}
void add(const string &str) {
add(str, nodes[0].exist);
}
void query(const string &str, const function<void(int)> &f, int str_index, int node_index) {
for (auto &idx : nodes[node_index].accept) f(idx);
if (str_index == str.size()) {
return;
} else {
const int c = str[str_index] - margin;
if (nodes[node_index].nxt[c] == -1) return;
query(str, f, str_index + 1, nodes[node_index].nxt[c]);
}
}
void query(const string &str, const function<void(int)> &f) {
query(str, f, 0, 0);
}
int count() const {
return (nodes[0].exist);
}
int size() const {
return ((int) nodes.size());
}
};
template<int char_size, int margin>
struct AhoCorasick : Trie<char_size + 1, margin> {
using Trie<char_size + 1, margin>::Trie;
const int FAIL = char_size;
vector<int> correct;
void build(bool heavy = true) {
correct.resize(this->size());
for (int i = 0; i < this->size(); i++) {
correct[i] = (int) this->nodes[i].accept.size();
}
queue<int> que;
for (int i = 0; i <= char_size; i++) {
if (~this->nodes[0].nxt[i]) {
this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
que.emplace(this->nodes[0].nxt[i]);
} else {
this->nodes[0].nxt[i] = 0;
}
}
while (!que.empty()) {
auto &now = this->nodes[que.front()];
correct[que.front()] += correct[now.nxt[FAIL]];
que.pop();
for (int i = 0; i < char_size; i++) {
if (now.nxt[i] == -1) continue;
int fail = now.nxt[FAIL];
while (this->nodes[fail].nxt[i] == -1) fail = this->nodes[fail].nxt[FAIL];
this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
if (heavy) {
auto &u = this->nodes[now.nxt[i]].accept;
auto &v = this->nodes[this->nodes[fail].nxt[i]].accept;
vector<int> accept;
set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));
u = accept;
}
que.emplace(now.nxt[i]);
}
}
}
map<int, int> match(const string &str, int now = 0) {
map<int, int> result;
for (auto &c : str) {
while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];
now = this->nodes[now].nxt[c - margin];
for (auto &v : this->nodes[now].accept) result[v] += 1;
}
return result;
}
pair<int, int> move(const char &c, int now) {
int sum = 0;
while (this->nodes[now].nxt[c - margin] == -1) now = this->nodes[now].nxt[FAIL];
now = this->nodes[now].nxt[c - margin];
sum += correct[now];
return {sum, now};
}
void init() {
this->nodes[this->root].count = 1;
}
mti nxxt;
void buildnexxt() {
int sz = this->nodes.size();
nxxt = mti(sz, vi(10));
rep(i, sz) {
rep(j, 10) {
nxxt[i][j] = this->nodes[i].nxt[j];
if (nxxt[i][j] == -1) nxxt[i][j] = nxxt[this->nodes[i].nxt[FAIL]][j];
}
}
}
ll moveone() {
int sz = this->nodes.size();
vl tmp(sz, 0);
rep(i, sz) {
if (this->nodes[i].flag) continue;
ll k = this->nodes[i].count;
repl(j, 1, 10) {
tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD;
}
}
ll ans = 0;
rep(i, sz) {
if (this->nodes[i].flag) continue;
ans = (ans + tmp[i]) % MOD;
this->nodes[i].count = tmp[i];
}
return ans;
}
ll moveall() {
int sz = this->nodes.size();
vl tmp(sz, 0);
rep(i, sz) {
if (this->nodes[i].flag) continue;
ll k = this->nodes[i].count;
rep(j, 10) {
tmp[nxxt[i][j]] = (tmp[nxxt[i][j]] + k) % MOD;
}
}
ll ans = 0;
rep(i, sz) {
if (this->nodes[i].flag) continue;
ans = (ans + tmp[i]) % MOD;
this->nodes[i].count = tmp[i];
}
return ans;
}
};
int main() {
//CFS;
int n;
ll l, r;
cin >> n >> l >> r;
vl f(2, 1);
while (f[f.size() - 2] < LINF - f[f.size() - 1]) {
f.push_back(f[f.size() - 2] + f[f.size() - 1]);
}
AhoCorasick<10, '0'> ac;
for (auto &x : f) {
cout << x << endl;
if (l <= x && x <= r) {
ac.add(to_string(x));
}
}
ac.build();
ac.buildnexxt();
ac.init();
ll ans = ac.moveone();
repl(i, 1, n) ans = (ans + ac.moveall()) % MOD;
cout << ans << endl;
return 0;
}