結果

問題 No.1269 I hate Fibonacci Number
コンテスト
ユーザー minato
提出日時 2020-10-24 13:50:41
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 3,000 ms
コード長 7,060 bytes
コンパイル時間 13,084 ms
コンパイル使用メモリ 299,932 KB
最終ジャッジ日時 2025-01-15 15:03:23
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef ONLINE_JUDGE
#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
constexpr char ln = '\n';
template<class Container> inline int SZ(Container& v) { return int(v.size()); }
template<typename T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }
template<class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;}
template<class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;}
struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//必要に応じて、len 、par などの情報を持たせる
template<class Char>
struct AhoCorasick {
	struct State {
		map<Char, int> nex;
		int link, last;
		State() : link(0), last(0) {}
	};
	vector<State> node;
	AhoCorasick() {
		node.emplace_back();
		node[0].link = -1;
	}
 
	int process(int cur, Char c) {
		while (~cur and !node[cur].nex.count(c)) cur = node[cur].link;
        if (~cur) return node[cur].nex[c];
        return 0;
	}
 
    int addChar(Char c, int cur = 0) {
        if (!node[cur].nex.count(c)) {
            node[cur].nex[c] = node.size();
            node.emplace_back();
        }
        return node[cur].nex[c];
    }
 
    template<class String>
	int addString(const String& s) {
		int cur = 0;
        for(const Char& c : s) {
            cur = addChar(c,cur);
        }
        node[cur].last = 1;
        return cur;
	}
 
	void build() {
		queue<int> que;
		for (auto& p : node[0].nex) que.emplace(p.second);
		while (!que.empty()) {
			int cur = que.front(); que.pop();
			for(auto& [c,nex] : node[cur].nex) {
				node[nex].link = process(node[cur].link,c);
                node[nex].last |= node[node[nex].link].last;
				que.emplace(nex);
			}
		}
	}
 
	State& operator[](int v) { return node[v]; }

	int size() { return int(node.size()); }
};

/////////////////////////////////////////////////////////////////////////////////////////

template<int m> 
struct ModInt {
  public:
    static constexpr int mod() { return m; }
    static ModInt raw(int v) {
        ModInt x;
        x._v = v;
        return x;
    }

    ModInt() : _v(0) {}
    ModInt(long long v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    unsigned int val() const { return _v; }

    ModInt& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    ModInt& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    ModInt operator++(int) {
        ModInt result = *this;
        ++*this;
        return result;
    }
    ModInt operator--(int) {
        ModInt result = *this;
        --*this;
        return result;
    }

    ModInt& operator+=(const ModInt& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    ModInt& operator-=(const ModInt& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    ModInt& operator*=(const ModInt& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    ModInt& operator^=(long long n) {
        ModInt x = *this;
        *this = 1;
        if (n < 0) x = x.inv(), n = -n;
        while (n) {
            if (n & 1) *this *= x;
            x *= x;
            n >>= 1;
        }
        return *this;
    }
    ModInt& operator/=(const ModInt& rhs) { return *this = *this * rhs.inv(); }

    ModInt operator+() const { return *this; }
    ModInt operator-() const { return ModInt() - *this; }

    ModInt pow(long long n) const {
        ModInt r = *this;
        r ^= n;
        return r;
    }
    ModInt inv() const {
        int a = _v, b = umod(), y = 1, z = 0, t;
        for (; ; ) {
            t = a / b; a -= t * b;
            if (a == 0) {
                assert(b == 1 || b == -1);
                return ModInt(b * z);
            }
            y -= t * z;
            t = b / a; b -= t * a;
            if (b == 0) {
                assert(a == 1 || a == -1);
                return ModInt(a * y);
            }
            z -= t * y;
        }
    }

    friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) += rhs; }
    friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) -= rhs; }
    friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) *= rhs; }
    friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) /= rhs; }
    friend ModInt operator^(const ModInt& lhs, long long rhs) { return ModInt(lhs) ^= rhs; }
    friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return lhs._v != rhs._v; }
    friend ModInt operator+(long long lhs, const ModInt& rhs) { return (ModInt(lhs) += rhs); }
    friend ModInt operator-(long long lhs, const ModInt& rhs) { return (ModInt(lhs) -= rhs); }
    friend ModInt operator*(long long lhs, const ModInt& rhs) { return (ModInt(lhs) *= rhs); }
    friend ostream &operator<<(ostream& os, const ModInt& rhs) { return os << rhs._v; }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
};
 
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;

using mint = ModInt<MOD>;

void yukico1269() {
    ll N,L,R; cin >> N >> L >> R;

    AhoCorasick<int> AC;

    ll f1 = 0, f2 = 1;
    while (true) {
        ll f = f1+f2;
        if (f > R) break;
        if (f >= L) {
            vector<int> num;
            for (ll a = f; a > 0;) {
                num.emplace_back(a%10);
                a /= 10;
            }
            reverse(all(num));
            AC.addString(num);
        }
        f1 = f2;
        f2 = f;
    }

    AC.build();
    int M = AC.size();
    vector<vector<int>> nex(M, vector<int>(10));
    rep(i,M) {
        rep(j,10) {
            nex[i][j] = AC.process(i,j);
            if (AC[nex[i][j]].last) nex[i][j] = -1;
        }
    }

    vector<mint> dp(M);
    dp[0] = 1;
    rep(i,N) {
        vector<mint> ndp(M);
        rep(j,M) {
            if (dp[j]==0) continue;
            rep(k,10) {
                if (~nex[j][k]) ndp[nex[j][k]] += dp[j];
            }
        }
        swap(dp,ndp);
    }
    mint ans = 0;
    rep(j,M) ans += dp[j];
    ans--;

    cout << ans << ln;
}

int main() {
    yukico1269();
}
0