結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
![]() |
提出日時 | 2020-10-23 23:42:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 3,000 ms |
コード長 | 5,382 bytes |
コンパイル時間 | 1,758 ms |
コンパイル使用メモリ | 125,268 KB |
実行使用メモリ | 62,336 KB |
最終ジャッジ日時 | 2024-07-21 13:45:00 |
合計ジャッジ時間 | 4,933 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional)#include <iostream>#include <iomanip>#include <cstdio>#include <string>#include <cstring>#include <deque>#include <list>#include <queue>#include <stack>#include <vector>#include <utility>#include <algorithm>#include <map>#include <set>#include <complex>#include <cmath>#include <limits>#include <cfloat>#include <climits>#include <ctime>#include <cassert>#include <numeric>#include <fstream>#include <functional>#include <bitset>using namespace std;using ll = long long int;using int64 = long long int;template<typename T> void chmax(T &a, T b) {a = max(a, b);}template<typename T> void chmin(T &a, T b) {a = min(a, b);}template<typename T> void chadd(T &a, T b) {a = a + b;}int dx[] = {0, 0, 1, -1};int dy[] = {1, -1, 0, 0};const int INF = 1LL << 29;const ll LONGINF = 1LL << 60;const ll MOD = 1000000007LL;void test() {vector<ll> fib(2, 1);for(int i=2; ; i++) {ll nxt_fib = fib[i-1] + fib[i-2];if(nxt_fib > (ll)1e18) break;else {fprintf(stderr, "fib[%d] = %lld\n", i, nxt_fib);fib.emplace_back(nxt_fib);}}}// ModInt beginusing ll = long long;template<ll mod>struct ModInt {ll v;ll mod_pow(ll x, ll n) const {return (!n) ? 1 : (mod_pow((x*x)%mod,n/2) * ((n&1)?x:1)) % mod;}ModInt(ll a = 0) : v((a %= mod) < 0 ? a + mod : a) {}ModInt operator+ ( const ModInt& b ) const {return (v + b.v >= mod ? ModInt(v + b.v - mod) : ModInt(v + b.v));}ModInt operator- () const {return ModInt(-v);}ModInt operator- ( const ModInt& b ) const {return (v - b.v < 0 ? ModInt(v - b.v + mod) : ModInt(v - b.v));}ModInt operator* ( const ModInt& b ) const {return (v * b.v) % mod;}ModInt operator/ ( const ModInt& b ) const {return (v * mod_pow(b.v, mod-2)) % mod;}bool operator== ( const ModInt &b ) const {return v == b.v;}bool operator!= ( const ModInt &b ) const {return !(*this == b); }ModInt& operator+= ( const ModInt &b ) {v += b.v;if(v >= mod) v -= mod;return *this;}ModInt& operator-= ( const ModInt &b ) {v -= b.v;if(v < 0) v += mod;return *this;}ModInt& operator*= ( const ModInt &b ) {(v *= b.v) %= mod;return *this;}ModInt& operator/= ( const ModInt &b ) {(v *= mod_pow(b.v, mod-2)) %= mod;return *this;}ModInt pow(ll x) { return ModInt(mod_pow(v, x)); }// operator int() const { return int(v); }// operator long long int() const { return v; }};template<ll mod>ModInt<mod> pow(ModInt<mod> n, ll k) {return ModInt<mod>(n.mod_pow(n.v, k));}template<ll mod>ostream& operator<< (ostream& out, ModInt<mod> a) {return out << a.v;}template<ll mod>istream& operator>> (istream& in, ModInt<mod>& a) {in >> a.v;return in;}// ModInt endusing mint = ModInt<MOD>;int nxt_state[750][10];mint dp[5010][750][2];int main() {// test();ll N, L, R; cin >> N >> L >> R;vector<string> pfx;auto add_str = [&](string pat) {if(stoll(pat) < L) return;if(R < stoll(pat)) return;for(int i=0; i<=(int)pat.size(); i++) {pfx.emplace_back(pat.substr(0, i));}};add_str("1");vector<ll> fib(2, 1);for(int i=2; ; i++) {ll nxt_fib = fib[i-1] + fib[i-2];if(nxt_fib > (ll)1e18) break;else {add_str(to_string(nxt_fib));fib.emplace_back(nxt_fib);}}pfx.emplace_back("");sort(pfx.begin(), pfx.end());pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());int M = pfx.size();vector<int> ng_state(M, false);for(int i=0; i<M; i++) {for(int k=1; k<(int)fib.size(); k++) {if(fib[k] < L or R < fib[k]) continue;string t = to_string(fib[k]);int lenA = t.length();int lenB = pfx[i].length();if(lenA <= lenB) {if(pfx[i].substr(lenB - lenA, lenA) == t) {ng_state[i] = true;}}}for(int c=0; c<10; c++) {string s = pfx[i] + (char)('0' + c); int k;while(true) {k = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();if(k < M and pfx[k] == s) break;s = s.substr(1);}nxt_state[i][c] = k;}}fill(dp[0][0], dp[N+1][0], mint(0));dp[0][0][0] = mint(1);for(int i=0; i<N; i++) {for(int j=0; j<M; j++) {for(int f=0; f<2; f++) {for(int k=0; k<10; k++) {int nj = nxt_state[j][k];if(ng_state[j] or ng_state[nj]) continue;if(f == 0 and k == 0) continue;int nf = f || (k > 0);dp[i+1][nj][nf] += dp[i][j][f];}}}}mint ans(0);for(int i=0; i<M; i++) {for(int j=1; j<=N; j++) {if(ng_state[i]) continue;ans += dp[j][i][1];}}cout << ans << endl;return 0;}